The coolest talk of this year's Blackhat must have been the one of Sean Devlin and Hanno Böck. The talk summarized this early year's paper, in a very cool way: Sean walked on stage and announced that he didn't have his slides. He then said that it didn't matter because he had a good idea on how to retrieve them.
He proceeded to open his browser and navigate to a malicious webpage. Some javascript there seemed to send various requests to a website in his place, until some MITM attacker found what they came for. The page refreshed and the address bar now whoed https://careers.mi5.gov.uk as well as a shiny green lock. But instead of the content we would have expected, the white title of their talk was blazing on a dark background.
What happened is that a MITM attacker tampered with the mi5's website page and injected the slides in a HTML format in there. They then went ahead and gave the whole presentation via the same mi5's webpage.
How it worked?
The idea is that repeating a nonce in AES-GCM is... BAD. Here's a diagram from Wikipedia. You can't see it, but the counter has a unique nonce prepended to it. It's supposed to change for every different message you're encrypting.
AES-GCM is THE AEAD mode. We've been using it mostly because it's a nice all-in-one function that does encryption and authentication for you. So instead of shooting yourself in the foot trying to MAC then-and-or Encrypt, an AEAD mode does all of that for you securely. We're not too happy with it though, and we're looking for alternatives in the CAESAR's competition (there is also AES-SIV).
The presentation had an interesting slide on some opinions:
"Do not use GCM. Consider using one of the other authenticated encryption modes, such as CWC, OCB, or CCM." (Niels Ferguson)
"We conclude that common implementations of GCM are potentially vulnerable to authentication key recovery via cache timing attacks." (Emilia Käsper, Peter Schwabe, 2009)
"AES-GCM so easily leads to timing side-channels that I'd like to put it into Room 101." (Adam Langley, 2013)
"The fragility of AES-GCM authentication algorithm" (Shay Gueron, Vlad Krasnov, 2013)
"GCM is extremely fragile" (Kenny Paterson, 2015)
One of the bad thing is that if you ever repeat a nonce, and someone malicious sees it, that person will be able to recover the authentication key. It's the H in the AES-GCM diagram, and it is obtained by hashing the encryption key K. If you want to know how, check Antoine Joux' comment on AES-GCM.
Now, with this attack we lose integrity/authentication as soon as a nonce repeats. This means we can modify the ciphertext in the middle and no-one will realize it. But modifying the ciphertext doesn't mean we can modify the plaintext right? Wait for it...
Since AES-GCM is basically counter mode (CTR mode) with a GMac, the attacker can do the same kind of bitflip attacks he can do on CTR mode. This is pretty bad. In the context of TLS, you often (almost always) know what the website will send to a victim, and that's how you can modify the page with anything you want.
Look, this is CTR mode if you don't remember it. If you know the nonce and the plaintext, fundamentally the thing behaves like a stream cipher and you can XOR the keystream out of the ciphertext. After that, you can encrypt something else by XOR'ing the something else with the keystream :)
They found a pretty big number of vulnerable targets by just sending dozen of messages to the whole ipv4 space.
My thoughts
Now, here's how the TLS 1.2 specification describe the structure of the nonce + counter in AES-GCM: [salt (4) + nonce (8) + counter (4)].
The whole thing is a block size in AES (16 bytes) and the salt is a fixed part of 4 bytes derived from the key exchange happening during TLS' handshake. The only two purposes of the salt I could think of are:
Pick the reason you prefer.
Now if you picked the second reason, let's recap: the nonce is the part that should be different for every different message you encrypt. Some increment it like a counter, some others generate them at random. This is interesting to us because the birthday paradox tells us that we'll have more than 50% chance of seeing a nonce repeat after \(2^{32}\) messages. Isn't that pretty low?
I've noticed that since I published the How to Backdoor Diffie-Hellman paper I did not post any explanations on this blog. I just gave a presentation at Defcon 24 and the recording should be online in a few months. In the mean time, let me try with a dumbed-down explanation of the outlines of the paper:
I found many ways to implement a backdoor, some are Nobody-But-Us (NOBUS) backdoors, while some are not (I also give some numbers of "security" for the NOBUS ones in the paper).
The idea is to look at a natural way of injecting a backdoor into DH with Pohlig-Hellman:
Here the modulus \(p\) is prime, so we can naturally compute the number of public keys (elements) in our group: \(p-1\). By factoring this number you can also get the possible subgroups. If you have enough small subgroups \(p_i\) then you can use the Chinese Remainder Theorem to stitch together the many partial private keys you found into the real private key.
The problem here is that, if you can do Pohlig-Hellman, it means that the subgroups \(p_i\) are small enough for anyone to find them by factoring \(p-1\).
The next idea is to hide these small subgroups so that only us can use this Pohlig-Hellman attack.
Here the prime \(n\) is not so much a prime anymore. We instead use a RSA modulus \(n = p \times q\).
Since \(n\) is not a prime anymore, to compute the number of possible public keys in our new DH group, we need to compute \((p-1)(q-1)\) (the number of elements co-prime to \(n\)). This is a bit tricky and only us, with the knowledge of \(p\) and \(q\) should be able to compute that.
This way, under the assumptions of RSA, we know that no-one will be able to factor the number of elements (\((p-1)(q-1)\)) to find out what subgroups there are. And now our small subgroups are well hidden for us, and only us, to perform Pohlig-Hellman.
There is of course more to it. Read the paper :)
If you want to generate good randomness, but are iffy about /dev/urandom because your machine has just booted, and you also don't know how long you should wait before /dev/urandom has enough entropy, then maybe you should consider using getrandom (thanks rwg!). From the manpage:
By default, getrandom() draws entropy from the /dev/urandom pool.
If the pool has not yet been initialized, then the call blocks
Also it seems like the instruction RDRAND on certain Intel chips returns "true" random numbers. It's also interesting to see that it was audited twice by Cryptography Research, which resulted in two papers, the recent one being in 2012 and done by Kocher et al: Analysis of Intel's Ivy Bridge Digital Random Number Generator.
Dear Mr.DAVID
I am learning about generating an elliptic curves cryptography , in your notes I find:-
JPF: Many people don’t trust NIST curves. How many people verified the curve generation? Open source tools would be nice.
Flori: people don't trust NIST curves anymore, surely for good reasons, so if we do new curves we should make them trustable. Did anyone here tried generating nist, dan, brainpool etc...? (3 people raised their hands).
Would you give me some reasons for generating our own curves? what are the good reasons that some people do not
trust on NIST CURVES?
your sincerely
hager
Hello Mr. HAGER
Well, the history of how standard curves were generated has been pretty chaotic, and djb has shown that this might be a bad thing for us in his Bada55 paper.
NIST says that they generated their curves out of the hash of a sentence that is unknown and lost. The german Brainpool curves seem to ignore their own standards on how to generate secure curves.
one of the standard Brainpool curves below 512 bits were generated by the standard Brainpool curve-generation procedure
So how bad is it? We know that choosing random parameters for your crypto algorithms can lead to unsecure or even backdoored constructions. See how to choose Sboxes in DES, how to choose nothing-up-my-sleeve numbers for hash functions, how to choose secure parameters for Diffie-Hellman, how Dual EC is backdoored if you know how the main points P and Q were generated, ...
Well, so far we don't really know. The fact that we haven't been able to crack any of the curves we use is "reassuring". I like to look at bitcoin as a proof that at least one of them hasn't been broken :) But as many researchers suspect, the NSA might be years ahead of us in cryptanalysis. So it is possible that they might have found one (or more) issues with elliptic curve cryptography, and that they generated "weak" curves before publishing them through NIST's standards.
So far, there hasn't been enough advances in ECC (a relatively old field in cryptography) to make you worried enough to generate your own curves. Some people do that though, but they know what they're doing. They even released a paper on how to generate safe curves using nothing-up-my-sleeves parameters. Like that, you can review the generation process and see that nothing was done to harm you.
Some people also worry about sparse primes, and that's one more paranoid reason to use random curves as above.
But seriously, if you don't want to go through all the trouble, you should probably start using one of the curve specified in this RFC: Curve 25519 or Curve 448. They use state-of-the-art research, reproducible generation and have been vetted by many people.
Blackhat and Defcon are almost here! I'll be landing there on Friday 29th and will give a crypto training at Blackhat, then on the 5th will give a talk at the Defcon Village track about Diffie-Hellman and backdoors.
If you have any interest in cryptography and want to meet up say the word! We should probably organize a drunk cryptographer evening (anyone interested?)
Also, I should be looking in what talks are interesting, if you think a particular one is please share in the comment section =)
I was at the offices of Braintree this evening, talking about the history of TLS, backdoors and Diffie-Hellman. If you missed it, my paper was released a few days ago and this is the talk that is packaged with it =)
my colleagues and I preparing the event in the beautiful atrium of Braintree
starting the talk!
Someone asked me for the slides, you can find them on the github repo. You can find the .keynote file as well containing videos (but you need osx).
I'll be looking into submitting this talk to conferences, if you have any idea where I'll be happy to hear suggestions =)
My latest whitepaper just got published on ePrint. It's available here.
Looking to seek answers to the recent Snowden revelations and the history of state agencies backdoors, this paper looks at what the secret spies might have been researching in order to find new ways to observe and tamper with the people's traffic. What if we just sabotaged one of the most trusted cryptographic algorithm of the last 40 years? What if we backdoored Diffie-Hellman?
Next week on wednesday NCC Group will host its second open forum in Chicago. And I'll be one of the speaker!
If you are interested in crypto, I'll be talking about backdoors and Diffie-Hellman. This will be the occasion of explaining what my latest whitepaper that was released today is about.
John Downey will also be talking about "Cryptography Pitfalls".
By the way, if you're interested in such events in Chicago. OWASP was today (and we even learned how to brew beer there). There are also other security related events that you can get update on from this twitter.
