Hey! I'm David, a security engineer at the Blockchain team of Facebook, previously a security consultant for the Cryptography Services of NCC Group. I'm also the author of the Real World Cryptography book. This is my blog about cryptography and security and other related topics that I find interesting.

I've Implemented a Coppersmith-type attack (using LLL reductions of lattice basis). It was done by Boneh and Durfee and later simplified by Herrmann and May. The program can be found on my github.

The attack allows us to break RSA and the private exponent d.
Here's why RSA works (where e is the public exponent, phi is euler's totient function, N is the public modulus):

\[ ed = 1 \pmod{\varphi(N)} \]
\[ \implies ed = k \cdot \varphi(N) + 1 \text{ over } \mathbb{Z} \]
\[ \implies k \cdot \varphi(N) + 1 = 0 \pmod{e} \]
\[ \implies k \cdot (N + 1 - p - q) + 1 = 0 \pmod{e} \]
\[ \implies 2k \cdot (\frac{N + 1}{2} + \frac{-p -q}{2}) + 1 = 0 \pmod{e} \]

The last equation gives us a bivariate polynomial \( f(x,y) = 1 + x \cdot (A + y) \). Finding the roots of this polynomial will allow us to easily compute the private exponent d.

The attack works if the private exponent d is too small compared to the modulus: \( d < N^{0.292} \).

To use it:

look at the tests in boneh_durfee.sage and make your own with your own values for the public exponent e and the public modulus N.

guess how small the private exponent d is and modify delta so you have d < N^delta

tweak m and t until you find something. You can use Herrmann and May optimized t = tau * m with tau = 1-2*delta. Keep in mind that the bigger they are, the better it is, but the longer it will take. Also we must have 1 <= t <= m.

you can also decrease X as it might be too high compared to the root of x you are trying to find. This is a last recourse tweak though.

Here is the tweakable part in the code:

# Tweak values here !
delta = 0.26 # so that d < N^delta
m = 3 # x-shifts
t = 1 # y-shifts # we must have 1 <= t <= m

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either "possibly in set" or "definitely not in set". Elements can be added to the set, but not removed (though this can be addressed with a "counting" filter). The more elements that are added to the set, the larger the probability of false positives.

One of my professor is organizing a CTF, it's in french (sorry), it will start next month and should last for a week, and... there might be a challenge I've made for them =). I don't know if it has been accepted but here you go: HackingWeek 2015 if you are interested and you can speak french

Thomas Ptacek had left Matasano, 2 years after selling to NCC, and I spotted him talking about a new "hiring" kind of company on hackernews... Well today they announced what is going to be a new kind of hiring process. After the revolution of education with Coursera and other MOOC (Massive Open Online Courses), now comes the revolution of hiring. It's called Starfighter and it will be live soon.

Because studying Cryptography is also about using LaTeX, it's nice to spend a bit of time understanding how to make pretty documents. Because, you know, it's nicer to read.

Here's an awesome quick introduction of Tikz that allows to make beautiful diagram with great precision in a short time:

And I'm bookmarking one more that seems go way further.

I stumbled on this funny job post from jeff jarmoc:

This thread will, no doubt, be dominated by posts with laundry lists of requirements. Many employers will introduce themselves by describing what they want from you. At Matasano, we're a little different. We like to start by telling you about us. This month, I want to try to do that by drawing analogy to Mission Impossible.
What made the original show so great is exactly what was lost in the 'Tom Cruise takes on the world' reboot. The original 1960's and 70's Mission Impossible was defined primarily by a team working together against all odds to achieve their objective. It acknowledged that what they were doing was improbable, and more so for a solo James Bond or Tom Cruise character. As a team though, each character an expert in their particular focus area, the incredible became credible -- the impossible, possible.

If you're up to date on crypto news you will tell me I'm slow. But here it is, my favorite explanation of the recent Freak Attack is the one from Matthew Green here

TLS uses a cipher suite during the handshake so that old machines can still chat with new machines that use new protocols. In this list of ciphers there is one called "export suite" that is a 512bits RSA public key. It was made by the government back then to spy on foreigners since 512bits is "easy" to factor.
The vulnerability comes from the fact that you can still ask a server to use that 512bits public key (even though it should have been removed a long time ago). This allows you to make a man in the middle attack where you don't have to possess a spoofed certificate. You can just change the cipher request of the client during the handshake so that he would ask for that 512bits key. 36% of the servers out there would accept that and reply with such a key. From here if we are in the middle we can just factor the key and use that to generate our own private key and see all the following exchange in clear.

someone asked on Quora: What can I learn/know right now in 10 minutes that will be useful for the rest of my life?

And someone delivered! It's called the peg method, and it allows you to remember words in the long term really quickly. I knew about other techniques like creating a story where each words is like a double linked list of event or using each words as obstacles in a mental path. But this one seems way more useful and practical. But contrary to the other techniques, you have to memorize a few things before being able to use it:

KASUMI is a block cipher used in UMTS, GSM, and GPRS mobile communications systems. In UMTS, KASUMI is used in the confidentiality (f8) and integrity algorithms (f9) with names UEA1 and UIA1, respectively. In GSM, KASUMI is used in the A5/3 key stream generator and in GPRS in the GEA3 key stream generator.

It seems to be some kind of glasses you wear so that cameras and facial recognition softwares won't recognize you, it works by displaying lights that are only visible to cameras and not human eyes

A long time ago, I think around 2007, I got violently addicted to RSS. I was subscribed to hundreds of different blogs about design, tech, web... One new story would pop in my feed every 5 minutes. I had to read everything and I felt stressed all the time. Clicking, reading, clicking, reading... If I wasn't in front of my computer I felt like I was missing out. I then decided to remove my RSS reader software and never touched a feed again. And for the past years my browsing habits have mostly narrowed down to hackernews and a reddit without any default subs. But now that I am studying crypto, I wanted to get more immersed in this world and I had the idea of using my tendency to get addicted for a good purpose. So I tried the latest recommended RSS readers (since google reader doesn't exist anymore) and I subscribed to every crypto/security blog I could find and I started reading. And since, I've been reading a lot. So I guess it works! I've been using Digg Reader mostly because of the ios app that is really good and also because when I have nothing to read I can dig into what's on my twitter.

I have collected a list of 60 blogs about cryptography and security. If you feel like one is missing or one shouldn't be here please tell me! The list is here