New Factoring Record

After a quiet interval of just two weeks shy of a decade, on December 2nd the team of F. Boudot, P. Gaudry, A. Guillevic, N. Heninger, E. Thomé and P. Zimmermann announced a new record in factoring length, factoring a number created as part of the RSA Factoring Challenge.

This number is 795 bits, up from the 768-bit number successfully factored into its two prime factors back in December, 2009. In the interval, several other challenge numbers were factored, but each one was actually shorter than 768 bits.

What does this say about the strength of public-key cryptography? ...not much, in my non-expert opinion. An increase of 27 bits over a decade is, well, 2.7 bits/year. The authors estimate that their computation should be 2.25 times harder than the 768-bit number, based on scaling of the number field sieve.  However, various improvements gave them an advantage, and the 4,000 CPU-core years expended on this was 3 times faster than would otherwise have been expected.

In the prior decade, 1999-2009, the record was raised from 512 bits to 768 bits, over 25 bits/year. So this appears to be quite a slowdown, with the 768-bit record having held for an extraordinarily long time. But, among other things, the cash prize was withdrawn when the RSA Challenge ended in 2007, so incentives to simply demonstrate larger and larger factoring have declined. Of course, that doesn't mean that research on the topic has ended.

So, as always an important milestone, but hard to assign too much importance to it, either positive or negative, in my opinion.

Bill Manning

This morning I talked to Julie Manning, Bill's wife. Bill died early Saturday morning, at home in Oregon.  Most of you know Bill was waiting for a new heart. He would perhaps have gotten one next month. I guess the old one just wouldn't hold out long enough.

I first met Bill in about 1995, when I returned to ISI after my first stint in Japan.  He had taken a position in the Los Nettos project at ISI, a regional network project in the days when Internet service and operations work was still heavily shared between business and academia.  Bill brought an operator's eye to the project, often seeing things differently from the researchers in the group.

Bill kept the most erratic hours of any non-student I've ever met.  He might be in the office at 2am or at 2pm, either was equally likely. I'd ask, "Bill, what time did you come in?" He'd reply, "10am."  "I was here before that, and you were already here, it must have been earlier."  "Greenwich Mean Time."

And in one phase of life, "Bill, where do you live?" "Seat 4A."  He would speculate about his average altitude and speed over the previous month.

And, like any good geek, Bill had a spectacular collection of tie-dye t-shirts.  He came by the look honestly: growing up in the Bay Area, he had actually snuck into Grateful Dead rehearsals held in a barn, and had traveled as a deadhead for a while.

At ISI, we called Bill "the bad idea fairy".  He always brought a slightly-off-kilter view of technical problems, which triggered endless discussions of fascinating, if usually implausible, alternatives.

He had the most broad-ranging musical tastes of anyone I knew, and would eat almost anything (though, like me, he didn't drink alcohol). I was often envious of his eating and musical experiences.  He certainly lived life to its fullest.

On one occasion, I recall, we were eating lunch in a Thai restaurant for the first time.  Bill called for the food "the way you'd make it in Thailand".  The waiter went back into the kitchen and came out with a few raw Thai chiles.  Bill ate one whole, without even breaking a sweat.  The owner of the restaurant immediately came out to see who was eating them.  Pam became a friend to our group.

On other occasions, when the waiter asked for his order, Bill would point to another person at the table, and say, "I'll have what she's having."  "Well, what is she having?" "I don't know, I haven't heard her say."  Once in a while, he would point to someone else in the restaurant and say, "I'll have what they are having."  It was funny and sometimes disconcerting, which was very Bill, and it was also his way of making sure he himself was eating (and thinking and doing) as broadly as possible, without getting stale.

Bill worked in a bakery before joining Texas Instruments and accidentally falling into computer networking.  (When we first met, he was commuting between Houston and L.A.; Julie and the kids were still in Houston.)  I believe he attended a series of colleges but never finished his bachelor's degree.  Just a few years ago, however, Jun Murai convinced him to get a Ph.D.; this took clearing administrative hoops to demonstrate that Bill's life experience matched that of a bachelor's degree, which it certainly did.  I was honored to be on his Ph.D. committee.  I literally created a "trouble ticket" accounting scheme to track change requests for his thesis.

Bill was a valued member of the WIDE Project here in Japan.  He worked with the DNS root operations group here, and participated in as many WIDE meetings as he could.  He also came to Keio University's Shonan Fujisawa Campus when he was in Japan, and one of the best things about Bill was how seriously he took the students and their work, treating them like adult colleagues.

Bill had friends on all seven continents, and for all I know on the International Space Station, as well. He was loved by us all.

Julie does not plan to have a funeral immediately, so there is no need for flowers or the like. The family may do a memorial service in Utah in the spring.

He was a unique and wonderful human being. And a good friend.
Rest in peace, Bill.

Quantum Conference Calendars

For reference, here is a calendar for upcoming quantum workshops and conferences that seem to be kept up to date:

• Quantum Technology Lab

(n.b.: I had a bad calendar listed here! My apologies. Use the above one, which includes great info at the bottom about predatory publishers and conferences.)

2.4 Linear Cryptanalysis

Linear cryptanalysis (LC) is a known plaintext attack, developed by Mitsuru Matsui in 1990 after being inspired by differential cryptanalysis.  The key(!)  idea is to build a linear approximation of an S box, allowing you to calculate possible keys in reverse more quickly.

If a cipher is good, every individual bit of the output should have a 50% probability of being 0 and a 50% probability of being 1. Likewise, there should be no obvious relationship between the input and output bits (e.g., "If the third input bit is 1, the seventh output bit is 0.")  However, it is possible that some combinations of bits don't appear with equal probability. For example, the bit string composed of the first and third input bits and the second and fourth output bits should have all sixteen combinations 0000, 0001, ..., 1111 with equal probability, but perhaps there is a bias.  If $P_i$ is the $i$th input plaintext bit and $C_i$ is the $i$th output ciphertext bit, we can construct an equation like

$L = P_1 + P_3 + C_2 + C_4$

(where '+' is modulo 2 addition, or XOR, here).  We say that such a combination has a bias if the probability of $L$ being 0 is noticeably different from 50%.

Such a combination is a linear combination of bits.  It is known (by whom?) that if the S-boxes in our cipher are fully linear, then the cipher can be easily broken.  Therefore, designers always use nonlinear S-boxes, but some bias such as this may be discoverable.

The basic idea of LC, then, is to find such sets of bits that exhibit some bias and use some algebra to recover a few bits of the subkey used in the last round of the cipher, rinse and repeat.  The trick is to find the right relationships showing a detectable bias, as was done with differential analysis.  This is done by examining the math of the S-boxes in detail; as far as I can tell, this phase of the operation is done by very smart humans.

If you can find a combination with a bias of $\epsilon$, then you need $1/\epsilon^2$ plaintext ciphertext pairs to find some bits of the subkey.

This is done by taking multiple expressions like the above, combining them using Matsui's "Piling Up Principle" where you track the biases multiplied together to make a linear approximation of the nonlinear S-box.

With this linear approximation, it is possible to find correlations between the output of the next-to-last round of the cipher and the original input qubits, from which it is possible to recover information about the subkey used in the last round of the cipher.

Ultimately, this doesn't give you complete information about the key or the plaintext, but substantially reduces the work needed to find the full key by guiding a search, rather than just testing keys at random.

Linear cryptanalysis is considered to be a very general technique, but I don't see extensive attempts to apply it to AES.  Indeed, AES (which was developed in the 1990s from the proposed cipher known as Rijndael) was developed specifically with the idea of not being vulnerable to either differential or linear cryptanalysis.

I found Heys' tutorial to be clear and helpful in understanding LC.

2.3 Differential Cryptanalysis

(I'm back, after a bit of a break. If you missed it, you can go back to the beginning of What Every Quantum Researcher and Engineer Should Know about Classical Cryptography.)

Biham and Shamir wrote a seminal paper, then an easy-to-read book on their rediscovery of differential cryptanalysis.  The goal of DC is to recover the key used for a session, so it is potentially far more serious than the birthday attack.

The book says, "An interesting feature of the new attack is that it can be applied with the same complexity and success probability even if the key is frequently changed and thus the collected ciphertexts are derived from many different keys."  That's pretty alarming.  This appears in a paragraph discussing chosen plaintext, so it may be restricted to that case.  I infer from this that rather than needing the cumulative accretion of information, each trial is independent.

The attack works with either chosen plaintext, in which the attacker says, "Please encrypt this message for me, and give me the ciphertext," or known plaintext, in which the attacker knows that the message is a repetition of "HEILHILTER", as figured prominently in the cracking of the Enigma machine in WWII.  Modern HTTPS (secure web browsing) connections and SMTP (email) connections have enough predictability in their content to provide a similar fulcrum for such a lever.  There is a substantial difference in the complexity of the two attacks (see Tab. 2.1 in the book).  Known plaintext takes waaay more trials to succeed.

The key idea is the construction of differentials (hence the name) from specific S boxes.  Take two possible inputs to an S box, $X_1$ and $X_2$.  We can assume the subkey has been XORed into both $X_1$ and $X_2$ already.  $Y_1$ and $Y_2$ are the corresponding outputs of the S box.  We know that if $X_1 = X_2$, then $Y_1 = Y_2$ and also $X_1 + X_2 = 0$ (again, here '+' is addition modulo two, or XOR).

For the total encryption algorithm, changing one bit in the input should result in about half the output bits changing.  The S box should be similar; small changes in the input should mean large changes in the output.  In fact, the S box is small enough that we can exhaustively analyze its inputs.  We also know some rules that were chosen during the design phase, for example, changing one bit in the six-bit input should result in changes to at two bits in the four-bit output.

So a differential table for each S box is constructed by listing all $2^6$ possible XORs $X_1 + X_2$, and collecting the stats on $Y_1 + Y_2$.  From the differences found here, we can work backwards to find with "high" probability (slightly higher than completely random, at any rate) some characteristics of the outputs of the previous round.

The overall attack is performed by encrypting a bunch of randomly-chosen pairs of plaintexts (chosen as a pair; first a completely random one, then a second by XORing in a specific value) and comparing their ciphertexts until we find an output pair of ciphertexts that fit comfortably with the difference tables we have pre-computed for the S boxes.  Repeat until we have built up some statistics about the right set of bits in the output, and from that we can take a probabilistic guess at the subkey in the last round.  Based on that guess, we can narrow down the set of subkeys for the next-to-last round, rinse and repeat.  It's still a computationally intensive, tedious process, but much less than brute force.  Roughly, the probability of getting the ciphertext pairs we need is proportional to $1/p_D$, where $p_D$ is the differential probability in the table we are looking for, which may be quite small. (This seems to me that keeping a history of things you've already tried would increase the probability of finding a pair you like, so I'm still puzzled by the assertion above that this works even if the key is being changed frequently.)

Ultimately, this attack is considered practical against ordinary DES. Biham and Shamir estimated (p. 8, p. 61) that DES and DES-like systems, even with the full sixteen rounds, could be broken using $2^{43}$ to $2^{47}$ chosen plaintext/ciphertext pairs.  With 8-byte blocks, that's encryption of 64 terabytes up to a petabyte.  If the system under attack can encrypt a 40Gbps link at line rate, that's only a few hours up to a couple of days of data.

Triple-DES would be much, much longer, but 3-DES is still considered obsolete due to the birthday paradox attack above.  AES is stronger against DC, so this attack is of less help against properly-implemented, modern systems.

I know this is a very rough explanation; I have only a wobbly understanding of the process myself!  The differential tables are pretty straightforward, once you understand them, but working from there to a full-on attack is a big jump.

Favorite Books of the Last Decade

It seems the height of hubris to declare the "best books of the decade", when I read perhaps three hundred in that time span, while a couple of million books are published each year, most in languages I can't read. But at the same time, it's kind of nice to look back and think about which ones I read that have stayed with me. Most of these are pretty obvious choices; I don't think I'm saying much controversial here. Links go to my Goodreads reviews, where available, though most of the time I don't really write formal reviews. Also, note that this is books I read last decade, but many of the books themselves are older.

• Best General Science/Space History/Memoir: Lab Girl (previous decade: Riding Rockets; Honorable Mention: The Big Picture, We Have No Idea)
• Best Novel by a Nobelist: One Hundred Years of Solitude (Honorable Mention by a non-Nobelist: The Sea of Fertility)
• Best Whatever the Heck This Is: Self-Reference ENGINE
• Best IT-Related Nonfiction: Superintelligence (Honorable Mentions: The Codebreakers, The Book of Why, Quantum Computing Since Democritus, The Golden Ticket) Not without significant shortcomings, but a great springboard for conversation; there is also an even longer version of my review of this somewhere...
• Best Space Opera/Hard SF: Ancillary Justice (Very Honorable Mention: Three Body Problem)
• Best Cyberpunk: Daemon and Freedom(TM)
• Best Fantasy/Speculative Fiction: The Fifth Season
• Best History/Analysis: Why Nations Fail
• Best History/Big Picture Narrative: The Civil War Trilogy Apparently I didn't write a review, but I loved these books. Stiff competition from others on WWI, WWII, and topics such as the Crusades, the history of Islam, and the fall of the Ottoman Empire, though.
• Best History/Tight Focus: Hidden Figures
• Best Mystery: The City and the City
• Best Hard Boiled/Noir:  The Maltese Falcon (I enjoyed rereading my own review! I should put in the effort more often.)
• Best Collection: The Found and the Lost

I'm sure I'll come back to this at some point and go, "Geez, what was I thinking when I left out...?!?" but this short list will have to do for now!