1
$\begingroup$

I can recover something trivial like a 16-bit AES key in practice. I'm confident that a 64-bit AES key can be recovered. However, I have been unable to find any documentation of the biggest AES key that anyone claims to have recovered in practice. Are such competitions held, and is there a recognized progress meter that is kept?

Edit: I'm talking about brute-forcing intentionally weakened keys, i.e. repeating the first X bits of the key to the end.

$\endgroup$
7
  • 3
    $\begingroup$ There is an active field that can be compared: bitcoin mining. At time of writing they reportedly perform $140\cdot10^{18}$ H/s where H is a SHA256d, that is two SHA-256, thus $>2^{92.8}$ SHA-256/year. $\endgroup$
    – fgrieu
    Nov 24, 2020 at 6:50
  • 4
    $\begingroup$ Also, AES keys (of any standard size: 128, 192 or 256-bit) are routinely recovered by means other than brute force, broadly speaking side channels, including Differential Power Analysis, cache line leakage, fault injection, probing, Van Eck phreaking, buffer overrun, testing what's in stack/memory, cold boot attack, post-it reading/snapping, looking thru insufficiently opaque envelopes, opening others; and (I imagine) wrench/rubber-hose cryptanalysis, and bribery. Plus attacking the RNG or password used for generation. $\endgroup$
    – fgrieu
    Nov 24, 2020 at 7:42
  • 3
    $\begingroup$ Nitpick: a key not of a standard size isn't an AES key. It could be a Rijndael key, but the Advanced Encryption Standard only has 128, 192, & 256 bit keys by definition. $\endgroup$ Nov 24, 2020 at 13:27
  • 1
    $\begingroup$ The most feasible attack on AES-128 is the multi-target attack, See a list in Has AES-128 been fully broken?. Any other attack is not feasible, yet! $\endgroup$
    – kelalaka
    Nov 24, 2020 at 16:05
  • 1
    $\begingroup$ Isn't copying the first 16 bits of an AES key repeatedly over the remaining every successive 16 bits effectively producing a 16 bit AES key, assuming you are letting the attacker know you did this? $\endgroup$ Nov 25, 2020 at 2:44

2 Answers 2

1
$\begingroup$

Are such competitions held, and is there a recognized progress meter that is kept?

No. It is generally believed that $2^{128}$ AES keyschedule and encryption operations are out of reach for just about anyone. If and when that changes and $2^{128}$ draws in to be a more realistic number perhaps people will do that.

However, I have been unable to find any documentation of the biggest AES key that anyone claims to have recovered in practice.

This is usually not an interesting publishable result unless you also have found some major optimization to some part of the computation and thus not very desirable to do for academics.


As for search speeds:

  • On a CPU - assuming you get lucky with instruction scheduling - one round of AES with a keyschedule computation (very optimistically) costs you about 3 CPU cycles on a single core. For each AES instance there are 10 such steps, so around 30 cycles overall for on-the-fly key scheduling and encryption of one block - using only throughput not latency numbers. This amounts to about 1-2 billion AES key tests per core per second on a modern CPU. Assuming it is one of the beefiest around it has 64 physical cores and two CPUs on a mainboard amounting to say 200 billion AES key tests per second per mainboard. Feasibly a determined attacker can acquire and operate say ten thousand such mainboards amounting to $2\times 10^{15}\approx 2^{50}$ key tests per second. Then a realistic upper bound for how long would want to have this hardware run non-stop would be say 10 years if determined which adds another factor of $\approx 2^{28}$ amounting in total to $2^{78}$ AES keys using 20,000 of the current beefiest CPUs run for 10 years with a highly optimized implementation.
  • As for GPUs: A top-end Nvidia Pascal GPU hits about 32GB/s of AES throughput. That is 2 billion AES instances per second without the keyschedule, with the keyschedule it will probably drop down to ~800 million AES instances per second. Even if we assume that later GPU generations give a 5x performance increase to this number we'd only be looking at the performance of 1-2 additional CPU cores for a lot more power draw, so this is likely not worth it.
  • As for FPGAs, this paper claims around 120Gb/s throughput from an FPGA that has ~150 thousand lookup tables. Nowadays there are FPGAs around that are 25x larger. Using the usual (optimistic) factor of 3 for the keyschedule we're looking at around 8 billion key tests per second and card. This might be worthwhile if you can cool it properly but chances are it's a better investment of power to use more CPUs (which draw comparably much).
  • As for ASICs, this paper claims $678\times 10^{-6}$ bits per clockcycle-gate as the best result (ish). Assuming a GPU-sized die running at say 1GHz this would amount to $2\times 10^{16}$ bits per second or $2^{47}$ AES instances per second. Dividing this by our usual factor yields about $2^{45}$ instances per second. Assuming then that you can in fact produce, power and cool such a large die and somehow stack say 8 into a server mainboard's PCIe slots it would give you $2^{48}$ tests per board or almost $2^{90}$ tests in 10 years using 10,000 boards with 8 GPU-sized dies each running at 1GHz for 10 years.
$\endgroup$
3
  • $\begingroup$ Kudos for the great work. For the ASIC section, the paper is interesting, but it considers a 65nm process, which is no longer state of the art (≈15 nm, with ≈7nm in sight; Apple's recent M1 is reportedly 5nm). And it reports 7.25nJ/bit, that is I think 928nJ/AES, to be compared to 0.015nJ/SHA256 (30 J/TSHA256d) for state of the art bitcoin mining according to this. Thus I'd crank about 16 bit (give or take 4) for good measure. $\endgroup$
    – fgrieu
    Nov 25, 2020 at 10:33
  • $\begingroup$ @fgrieu my calculation doesn't use the energy numbers but rather only the area numbers and I calculated with 30B GEs, so the energy improvements shouldn't factor in here? $\endgroup$
    – SEJPM
    Nov 25, 2020 at 10:35
  • $\begingroup$ In ASIC design dominated by logic, size matters. The number of GE for a given silicon area is supposed to grow nearly as size^-2, thus there's a gap of like x16 in the GE between 65 nm and 15nm when die size, not energy, is the limit. I suspect that careful placement and sizing of individual simple gates is used in things like ASICs for bitcoin mining, and also makes a big difference in both silicon area, and energy. In such designs, energy is the essence, because that's often the design limit, and a lot of the cost comes from the energy, and the hardware to dissipate heat from the silicon. $\endgroup$
    – fgrieu
    Nov 25, 2020 at 11:11
0
$\begingroup$

I presume when you say you can "recover" 16 bit keys you mean by brute forcing. That isn't really recovering a key in the sense of a cryptographic break. Obviously all keys can be recovered that way, just in an insurmountable time.

The longest key that can be recovered is the longest possible key (256 bit), which can be recovered quicker than simple brute force in just over 2^252 time and with 2^40 data.

There is more here.

$\endgroup$
9
  • $\begingroup$ And if you do not mean 'by bruteforcing' then there exist different avenues by which you can attack AES. For example, if you had access to a 'padding oracle' or some sort, then you could perform a padding oracle attack. Depending on the implementation, there could also be side-channel attacks, such as timing side channel attackers performed. $\endgroup$
    – SeesSound
    Nov 24, 2020 at 14:15
  • $\begingroup$ @SeesSound The side-channel attacks seem to mainly be on particular implementations of AES, which I think is slightly different. In terms of their requirements (not their complexity obviously), some of those attacks are verging on watching a user type their password. $\endgroup$
    – Modal Nest
    Nov 24, 2020 at 14:37
  • $\begingroup$ @SeesSound padding oracle is not revealing the key. It is just a decryption oracle. $\endgroup$
    – kelalaka
    Nov 24, 2020 at 16:10
  • $\begingroup$ Just to be clear: the attack of cost $2^{252}$ against a 256-bit key described in the linked paper is entirely theoretical. Same for the one recovering a 128-key in $2^{126}$ steps. They have not recovered an initially unknown key in practice. In my opinion it's highly unlikely that it's possible to carry even the later attack within 2040. $\endgroup$
    – fgrieu
    Nov 24, 2020 at 17:07
  • $\begingroup$ To add to the @fgrieu comment above, the attack on a 128-bit key would take billions of years and 9007TB of storage space. $\endgroup$
    – Modal Nest
    Nov 24, 2020 at 17:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.