Hey! I'm David, the author of the Real-World Cryptography book. I'm a crypto engineer at O(1) Labs on the Mina cryptocurrency, previously I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.
I asked some questions to one of the co-author Adwait Nadkarni, I thought that it might be interesting to others:
But offline attacks can also be much harder, because they require either trying every single possible encryption key, or figuring out the user’s passcode and the device-specific key (the unique ID on Apple, and the hardware-bound key on newer versions of Android).
Q: I don't understand why you would have to guess that HBK, can't you just access it on the phone?
A: Thats a good question. To prevent the security from only being dependent on the user-supplied passcode, the HBK is supposed to be inaccessible from most software, similar to the iOS device-specific UID. That is, the HBK is supposed to be accessible only via the trusted executable environment (TEE), that is isolated on a different microprocessor. Untrusted software (even with compromise of the main kernel) is not supposed to be able to directly access the HBK.
That said, the reality is manufacturer-dependent. The TEE on different devices has been repeatedly compromised (Qualcomm TEE implementation compromised in 2014, HTC in 2015, etc.). Thus, there is threat of software compromise that may allow the attacker to retrieve or misuse the HBK.
Q: Is the secure enclave on the recent iPhones that TEE? Does that mean that most phones are vulnerable to offline brute force attacks? (since most phone don't have TEE (I'm not sure about that) and have a 4-6 digit PIN instead of an alphanumeric password)
A: The TEE is for Android; iOS uses secure enclave similarly. Most phones that do not use a device-specific key (i.e., old Android devices that run <Android 4.4, very old iOS devices) are vulnerable to offline brute-force attacks. Most phones (even old ones like our Nexus 4) do have TEE.
We built our own MDM application for our Android phone, and verified that the passcode can be reset without the user’s explicit consent; this also updated the phone’s encryption keys. We could then use the new passcode to unlock the phone from the lock screen and at boot time
Q: if you do that, the content on the phone would have to be decrypted with the real passcode and re-encrypted with your new passcode. I would imagine that the real passcode is not stored anywhere (there should be a password hash stored instead for verification only), so how does that technique works for the decryption phase? (don't know if the question is clear enough)
A: The phone is not directly encrypted with the passcode, but with a randomly generated DEK. The DEK is then encrypted with the KEK, which in turn is generated from the passcode and the HBK. Now, when the passcode is changed, the phone decrypts the DEK with the old KEK, then recreates the new KEK with the new passcode and HBK, and re-encrypts the DEK with the new KEK. Data is not touched when the passcode changes.
Q: so, specifically then, how does the phone uses the old KEK if it doesn't have the old passcode?
A: The old KEK is not created on the fly, but stored in the hardware-backed keystore (accessible only via the TEE). The TEE can retrieve it to decrypt the encrypted DEK.
Generally, operating system software is signed with a digital code that proves it is genuine, and which the phone requires before actually installing it.
this part made me wonder, what if we used lasers? Fault attacks are a big thing in the smart card industry, why is no one talking about it for cellphones? This prompted me to ask Frederico Menarini from Riscure:
Q: In iOS or Android if you want to update the phone, the update needs to be signed with Apple or Google or Samsung, etc... update key. But what you could do if you could mount a fault attack (lasers?) would be to target the point where the cellphone refuses the patch because of a false signature.
A: In principle, fault attacks are possible on phones – nothing prevents it and the scenario you described is valid. Laser attacks might be challenging though because certain chips use package-on-package or chip stacking, which means that you might not be able to directly affect the CPU using light.
In general attacking mobile phone chips will be complicated because they run at extremely high frequencies compared to smartcards (smartcards rarely run faster than 50 MHz) and because the feature size is much smaller (state of the art in smartcards is 90nm, which makes targeting the right area of the chip with a laser easier).
Here's a little demo of my work in progress research =)
The top right screen is the client, the bottom right screen is the server. I modified two numbers in some Socat file (hopefully it will be one number soon) and the backdoor is there. It's a public value and both the server and the client can generate their own certificates and use them in the TLS connection. For simplicity I don't do that, but just know that it would change nothing.
To get a Man-in-the-middle position I took the simplest approach I could think of: the screen on the left is a proxy, the client connect to the server through the proxy.
You will see that the proxy on the left will start parsing the server and the client packets as soon as it sees a TLS handshake. It then collects the server and the client Randoms, the server and the client DH public keys, and the DH parameters of the server to check if the backdoor is there. You will see a red message displaying that indeed, the backdoor is present.
For simplicity again (this is a proof of concept) I only use TLS 1.2 with AES128-CBC as the symmetric cipher and SHA-256 as the hash function used in the PRF/MAC/etc...
In a few seconds the premaster key, then the master key, then the MAC and encryption keys are computed and the traffic is then decrypted live.
Got my graphic tablet back, needed to do a small video to get back into it so I made something on Pollard's p-1 factorization algorithm:
You can find the records on factoring with p-1 on loria.fr, the biggest prime factor found was of 66 digits (~220bits) using B1=10^8 and B2=10^10. But people have been using bigger parameters like B1=10^10 and B2=10^15. It doesn't really make sense to continue using p-1 after that, and more efficient algorithms that still have a complexity tied to the size of the smallest factor exist. The Elliptic Curve Method (Or Lenzstra factorization method) is one of them, and is carrying the same ideas as p-1 in the elliptic curves.
In the video I also don't talk about B2. This is if you have a factorization of p-1 that is B1-powersmooth, except for a large single prime. You can just set a B2 which would be larger than this last factor and try every factor between B1 and B2. There are some optimizations that exist to do that faster instead of doing it naively but this is it.
I have this list of papers that is accumulating in a folder. After an idea of @gtank I decided to print the whole (~150 two-sided pages) and go to my local UPS store to bind it for ~8$.
I'm not posting the pdf I printed here, but I made it with pdfjoin --paper letterpaper --rotateoversize false *, could have used pdfbook to make it smaller but after printing a few pages I felt that it would be too small for my weary eyes (now I sound like an old bag).
here's the list of the papers I printed. They all seem like you can print them without going to jail.
Once we are done with the handshake, both parties are now holding the same set of keys. Right after the Server sends its ChangeCipherSpec message it starts encrypting. Right after the Client sends his own ChangeCipherSpec he starts encrypting his messages as well.
The encrypted records still start with the type of record, the TLS version and the length of the following bytes in clear. The rest is encrypted.
We won't talk about compression because there are a bunch of vulnerabilities that should make you think twice about using compression. So here it is, null! (more about that)
struct {
ContentType type;
ProtocolVersion version;
uint16 length;
select (SecurityParameters.cipher_type) {
case stream: GenericStreamCipher;
case block: GenericBlockCipher;
case aead: GenericAEADCipher;
} fragment;
} TLSCiphertext;
So as I said, we start with the type, the version and the length.
Right after the CipherSpecChange both parties will send an encrypted handshake message (a MAC of the whole transcript to authenticate the handshake), but most of the messages after will be encrypted Application data messages containing the real communications we want to protect.
0x17 is the byte for application data, then we have the TLS version, for TLS 1.2 it is 0x0303 (don't bother), then we have the length of the fragment which is described below for the AES-CBC case.
So in the case of AES-128, you would have an IV of 16 bytes followed by the encrypted data.
Yup, the MAC is not here because it is encrypted. TLS is a MAC-then-encrypt construction (...), you can do encrypt-then-MAC in practice but through an extension (cf. RFC 7366).
The rest is pretty straight forward, after decryption of the block-ciphered structure you remove the padding, check the MAC, use the content.
I just realized one more thing in TLS that doesn't make sense (besides the fact that different versions of TLS have different PRFs). Here's RFC 5246 (the RFC on TLS 1.2) on how to use the PRF transform your pre-master key into a master key:
Here's the same RFC on how to use the PRF to transform your master key into your 4 or 6 keys:
Noticed anything?
Took me some time, the first takes the server random appended to the client random, while the second takes the client random appended to the server random. I'm willing to bet this is not to circumvent any attack but rather to confuse the implementer...
Everything you want to know about TLS 1.2 is in RFC 5246. But as you may know, if you've read RFCs before, it is not easy to parse (plus they have some sort of double spaces non-sense).
Before we can encrypt/MAC everything with keys to secure our connection, we need to go over a key exchange called the Handshake to safely agree on a set of keys for both parties to use. The handshake can currently use 5 different algorithms to do the key exchange: RSA, Diffie-Hellman, Elliptic Curve Diffie-Hellman and the ephemeral versions of the last two algorithms.
This blogpost is about what happens between this key exchange and the encryption/authentication of data.
The Pre-Master Secret
The pre-master key is the value you directly obtain from the key exchange (e.g. \(g^{ab} \pmod{p}\) if using Diffie-Hellman). Its length varies depending on the algorithm and the parameters used during the key exchange. To make things simpler, we would want a fixed-length value to derive the keys for any cipher suite we would want to use. This is the reason behind a pre master secret. The fixed-length value we'll call master secret. Here the RFC tells us how to compute it from the pre-master secret after having removed the leading zeros bytes.
The two random values ClientHello.random and ServerHello.random, sometimes called "nonces", are randomly generated and sent during the ClientHello of each parties. This is to bound the soon-to-be master key to this session. PRF stands for Pseudo-random function, basically some concrete construction that emulates a random oracle: given an input will produce an output computationally indistinguishable from a truly random sequence. But let's move on, and we will see later what exactly is that PRF.
The Master Secret
A master secret is always 48 bytes. So now that we have a fixed length value, we can derive 4 keys from it:
client_write_MAC_key
server_write_MAC_key
client_write_key
server_write_key
As you can probably guess, MAC keys are for the authentication and integrity with whatever MAC algorithm you chose in the cipher suite, write keys are for the symmetric encryption.
Interestingly, two keys are generated for every purpose: one key per side. This is mostly by respect of good practices. Always segregate the use of your keys.
The symmetric ciphers chosen in the handshake will dictate how long these keys we generate need to be. Note that AEAD ciphers that combine both authentication and encryption will not need MAC keys but will need two other keys instead: client_write_IV and server_write_IV. This is because their MAC keys are directly derived from the encryption keys.
The same PRF we used on the pre-master key will be used on the master-key over and over until enough bytes have been created for the keys. From the section 6.3 of the RFC:
OK. Now that we got a nice global view of the process, let's dig deeper. The PRF used in TLS 1.2 is discussed here. It is quite different from the PRF used in TLS 1.1, see here.
Remember, for example how it was used to transform the pre-master key into a master key:
where + indicates concatenation, A() is defined as:
A(0) = seed
A(i) = HMAC_hash(secret, A(i-1))
This was a copy/paste from the RFC. To make it clearer: We use the label string ("master secret" in our example) concatenated with the two peers' random values as a seed.
We then MAC the seed with our pre-master secret as the key. We use the first output. Iterating the MAC gives us the subsequent values that we can append to our output.
\[ output = u_1 , u_2 , \cdots \]
This goes on and on until the output is long enough to cover the 48 bytes of the master key (or the 4 keys if we're applying to PRF on the master key).
If P_256 is being used, then SHA-256 is being used. This means the output of HMAC will be 256 bits (32 bytes). To get the 48 bytes of the master key, two iterations are enough, and the remaining bytes can be discarded.
I'm doing some tests on how Pollard Rho performs. I implemented the thing in Sage here and it doesn't perform that well I found. Pollard Kangaroo is also bad, but that must come from my implementation (I didn't really go further here since I don't really need Kangaroo: I already know the order + the value I'm looking for is not in any particular interval)
old_rho is Pollard rho, rho_lambda is the mislabeled Pollard Kangaroo algorithm, trials is the simple enumeration.
