Let's build an OS: crypt(3) is a bit weird

Let’s go on an adventure. I’ve learnt a lot more Rust over the last year, and I want to get back into writing properly, so my plan is to write a Linux Operating System. While writing it, I’ll be taking notes in my repo - https://github.com/sinkingpoint/qos/tree/main/notes . And every now and then formalising them into more structured blog posts over here, once I’ve learnt enough to make something interesting.

Recently, I went about implementing a login system for our operating system. I had a general idea of how to do this - users are stored in /etc/passwd, password hashes are stores in /etc/shadow, so we should read a username and password from the terminal, check the password against the password hash, and log the user in if it’s correct. Sounds simple enough, right? Well… there’s a surprising amount of complexity in that “check the password against the password hash” step, and to reveal it we’re going to have to talk about crypt(3).

crypt(3)

For the uninitiated, crypt(3), or simply crypt (the (3) comes from the fact that it can be found in the third chapter of the man pages) is a function provided by libcrypt that implements password hashing. At a very high level, you give it three bits of information: The “salt” (basically a randomly generated string), the “password”, and the “algorithm”, and it gives you back a hashed version of that information. You can see these in /etc/shadow. They look like this (⭐ for you if you can crack it):

$6$6K5C/5JmLlz2u620$zdVIE6PI0EpEtinzxU8eo7NIncxRnMCTZgIltb9voa8.YktocGmjUQp2RdENvWj0LV/sGt1NnGMj9Xpjvga4e/

Which can be split out into three parts:

• 6 - the algorithm (or “id”)
• 6K5C/5JmLlz2u620 - the salt
• zdVIE6PI0EpEtinzxU8eo7NIncxRnMCTZgIltb9voa8.YktocGmjUQp2RdENvWj0LV/sGt1NnGMj9Xpjvga4e/ - the hash

I’m not looking to be too flexible in my implementation - my plan is to stick with SHA2 variants (SHA256 and SHA512).

How to crypt

I’ve implemented a few auth systems in my time. Generally, when I’ve wanted to hash a password, I’ve taken an algorithm such as SHA512, and fed a concatenation of the salt and the password into the hashing algorithm and used that as my hash. For example, sha512(salt + password). If we take our above example, with a salt of 6K5C/5JmLlz2u620 and a password of test we get 928f9a61f04a7ceed36136ddd6018ee28b3e1214148b5bae897d9518f52a5bef2cce10e57e5d2f0d973b5616f77d50729369897c660cae499c8b5efc53bf3d34 (hex encoded). Hrmm. That’s not what we have above. In fact, it’s way longer, and wrong. And now we get into the weirdness of crypt(3).

Encoding

The first thing we can note is that that hash is definitely not the right encoding. SHA512 hashes are (perhaps obviously) 512 bits long. The above hash (928f9a61f04a7ceed36136ddd6018ee28b3e1214148b5bae897d9518f52a5bef2cce10e57e5d2f0d973b5616f77d50729369897c660cae499c8b5efc53bf3d34) is 129 characters which means it’s using 4 bits per character (give or take). 4 bits means that we have a hex encoding! If we look at our target hash, that’s 87 characters long. That means we’re using 6 bits (again, give or take) per character - that’s a base64 encoding! So our first step is to work out what base64 alphabet to use. It’s definitely not the RFC4648 standard (our hash contains ‘.’ and ‘/’, rather than ‘.’ and ‘+’). We can look at OpenBSD’s source code to find that the alphabet used is ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789. We can turn our string into that like so:

>>> import base64
>>> string = '928f9a61f04a7ceed36136ddd6018ee28b3e1214148b5bae897d9518f52a5bef2cce10e57e5d2f0d973b5616f77d50729369897c660cae499c8b5efc53bf3d34'
>>> b = bytes.fromhex(string)
>>> base64.b64encode(b, b'./')
b'ko.aYfBKfO7TYTbd1gGO4os.EhQUi1uuiX2VGPUqW.8szhDlfl0vDZc7Vhb3fVByk2mJfGYMrkmci178U789NA=='

Hrmm. That’s still not correct. There’s obviously more than just an encoding issue going on.

Madness

Beyond encoding, there’s only one other step that might be an issue - the actual hashing itself. Maybe it isn’t as simple as a concatenation followed by a hash? Let’s refer to the source code aga… Oh. So it turns out that crypt does something wild with SHA2 hashes (and others, although they use a subtely different procedure). Instead of just one hash, it actually does a bunch of them, feeding them into each other like some sort of gordian knot. Following that procedure, we get a bunch of steps:

• Add the password to a hash (A)
• Add the salt to the hash (A)
• Add the password to a hash (B)
• Add the salt to the hash (B)
• Add the password to a hash again (B)
• Add hash B to hash A
• For every bit of the password, if it’s a 1, add hash B to hash A, otherwise add the password to hash A
• For every byte in the password, add the password to a hash (P)
• 16 + (the first byte of A as an int) times, add the salt to a hash (S)
• Add the salt to DS
• N times, if N is even, add hash C to a hash (NC), otherwise add P to the hash. If N is divisible by 3, add S to the hash. If N is divisible by 7, add P to the hash. (C)
• Base64 encode C as the final output.

This procedure can also be found in a(the?) spec. This is kind of nuts, right? Where did this even come from? We can look at the story straight from the author who unfortunately doesn’t provide much context beyond linking to the original PR. I suspect that this might be just be made out of whole cloth. Either way, we can slap together a direct rust translation of that code pretty quickly:

let mut digest_a = Vec::new();

// the password string is added to digest A.
digest_a.extend_from_slice(password);

// the salt string is added to digest A.
digest_a.extend_from_slice(salt);

// start digest B.
let mut digest_b = Vec::new();
// add the password to digest B.
digest_b.extend_from_slice(password);
// add the salt string to digest B.
digest_b.extend_from_slice(salt);
// add the password again to digest B.
digest_b.extend_from_slice(password);

// finish digest B.
let digest_b = digest::digest(algorithm, &digest_b);

// For each block of 32 or 64 bytes in the password string (excluding
// the terminating NUL in the C representation), add digest B to digest A.
// For the remaining N bytes of the password string add the first
// N bytes of digest B to digest A.
digest_a.extend(digest_b.as_ref().iter().cycle().take(password.len()));

// For each bit of the binary representation of the length of the
// password string up to and including the highest 1-digit, starting
// from to lowest bit position (numeric value 1):
let mut len = password.len();
while len > 0 {
    if len & 1 == 1 {
        // a) for a 1-digit add digest B to digest A.
        digest_a.extend(digest_b.as_ref());
    } else {
        // for a 0-digit add the password string.
        digest_a.extend_from_slice(password);
    }

    len >>= 1;
}

// finish digest A
let digest_a = digest::digest(algorithm, &digest_a);

// start digest DP
let mut digest_dp = Vec::new();

// for every byte in the password (excluding the terminating NUL byte
// in the C representation of the string) add the password to digest DP.
for _ in 0..password.len() {
    digest_dp.extend_from_slice(password);
}

// finish digest DP.
let digest_dp = digest::digest(algorithm, &digest_dp);

//  produce byte sequence P of the same length as the password where
//  a) for each block of 32 or 64 bytes of length of the password string
//  the entire digest DP is used
//  b) for the remaining N (up to  31 or 63) bytes use the first N
//     bytes of digest DP
let p = digest_dp
    .as_ref()
    .iter()
    .cycle()
    .take(password.len())
    .collect::<Vec<_>>();

// start digest DS
let mut digest_ds = Vec::new();

// repeat the following 16+A[0] times, where A[0] represents the first
// byte in digest A interpreted as an 8-bit unsigned value add the salt to digest DS.
for _ in 0..16 + digest_a.as_ref()[0] {
    digest_ds.extend_from_slice(salt);
}

// finish digest DS.
let digest_ds = digest::digest(algorithm, &digest_ds);

// produce byte sequence S of the same length as the salt string where
// a) for each block of 32 or 64 bytes of length of the salt string the entire digest DS is used
// b) for the remaining N (up to  31 or 63) bytes use the first N bytes of digest DS
let s: Vec<u8> = digest_ds.as_ref().iter().cycle().take(salt.len()).cloned().collect();
let mut previous_digest = digest_a;

// repeat a loop according to the number specified in the rounds=<N>
// specification in the salt (or the default value if none is
// present).  Each round is numbered, starting with 0 and up to N-1.

// The loop uses a digest as input.  In the first round it is the
// digest A. In the latter steps it is the digest
// produced in step 21.h of the previous round.  The following text
// uses the notation "digest A/C" to describe this behavior.
for round in 0..rounds {
    // start digest C
    let mut digest_c = Vec::new();

    if round % 2 == 1 {
        // for odd round numbers add the byte sequense P to digest C.
        digest_c.extend_from_slice(&p);
    } else {
        // for even round numbers add digest A/C.
        digest_c.extend(previous_digest.as_ref());
    }

    // for all round numbers not divisible by 3 add the byte sequence S.
    if round % 3 != 0 {
        digest_c.extend(&s);
    }

    // for all round numbers not divisible by 7 add the byte sequence P.
    if round % 7 != 0 {
        digest_c.extend_from_slice(&p);
    }

    if round % 2 == 1 {
        // for odd round numbers add digest A/C
        digest_c.extend(previous_digest.as_ref());
    } else {
        // for even round numbers add the byte sequence P
        digest_c.extend_from_slice(&p);
    }

    // finish digest C.
    let digest_c: Vec<u8> = digest_c.into_iter().cloned().collect();
    previous_digest = digest::digest(algorithm, &digest_c);
}

And now we can login:

SeaBIOS (version 1.16.3-1fc39)
iPXE (https://ipxe.org) 00:03.0 CA00 PCI2.10 PnP PMM+7EFCBF30+7EF0BF30 CA00
Booting from ROM...
Probing EDD (edd=off to disable)... ok
login: colin
password:
Welcome to qos, colin!

$

Pretty exciting stuff! Now that we can log in, we have a whole world in front of us. My first step is making a proper init system that can start the login program, and then maybe a logging daemon to capture system logs?