16
$\begingroup$

Out of curiosity why we can't implement AES 512 key size?

Please explain somehow i can understand! I'm not an expert.

$\endgroup$
  • $\begingroup$ There is a similar question here crypto.stackexchange.com/questions/2486/… $\endgroup$ – Guut Boy Nov 14 '14 at 17:11
  • $\begingroup$ AES-like block cipher used in Whirlpool hash has 512-bit block size and key size. $\endgroup$ – LightBit Nov 14 '14 at 19:41
  • 1
    $\begingroup$ Rijndael can be extended to 512-bit keys, I have done so using 22 rounds, however significant modifications are required to the key schedule for it to be secure $\endgroup$ – Richie Frame Nov 14 '14 at 21:35
  • $\begingroup$ @RichieFrame Interesting. Any further info anywhere on these mods? $\endgroup$ – Paul Uszak Jun 1 '18 at 11:29
  • $\begingroup$ @PaulUszak If I remember correctly, the most simple method was to generate substantially more round keys, and skip 4 of them, so 1st, 6th, 11th for rounds 0,1,2. This allows the same fast rolling generation as the original, even if the linearity is suboptimal. The better method is a new key schedule that uses the round function itself $\endgroup$ – Richie Frame Jun 2 '18 at 1:56
38
$\begingroup$

We can't implement "AES 512 key size" because AES is defined for key sizes $k\in\{128,192,256\}$ bits only; much like we can't make a bicycle with 3 wheels.

I see no reason why we would want to define an AES variant with 512-bit key size (since AES-128 is safe enough for anything foreseeable most current applications except those that require huge security margins, AES-192 is more than enough for the most demanding ones, and AES-256 more than overkill). However we could define an AES variant with 512-bit key size. If we stick to the 128-bit block size, the two choices we have to make are:

  • How many rounds we should use; since the number of rounds in standard AES is $r=k/32+6$, anything even from $r=14$ (for performance and subkeys space comparable to AES-256, at the expense of resistance to related-key attacks much lower than AES-256) to $r=24$ (as a paranoia damper) seems justifiable.
  • How we would generate the $4(r+1)$ 32-bit words forming the $(r+1)$ 128-bit round subkeys out of the 512-bit key. By analogy with standard AES, the first 16 such words should be right from the key. I won't venture further.

The question seems to have been motivated by a "paper" titled AES Algorithm Using 512 Bit Key Implementation for Secure Communication (I'll charitably not mention the authors) which presents an AES variation with 512-bit key and block size, best summarized as: AES-128 with $8^2$ bytes wherever the original has $4^2$, an idea that at least could be made to work. However the "paper" has blatant issues:

  1. The "paper" present as "drawback" of AES-256 (which uses 14 rounds) that a 9-round variant is vulnerable to a related-key attack with $2^{224}$ works; yet it introduces a 10-round AES variant without the slightest justification that it will resist similar attacks.
  2. The aim is "higher level of security throughput", without attempt of definition; and doing so "without increasing overall design area as compared to the original 128 bit AES", while the state of the proposed algorithm (thus number of D latches in an hardware implementation) is 4 times that of AES-128, for both key and data.
  3. The drawing of the byte substitution step clearly shows a 4x4 grid of bytes holding "an array of 64 bytes".
  4. There is the same issue in the "shift row" step (to be read as ShiftRows), and the drawing gets confusing, since the line with $s_3$ is shown right-rotated by 1 step, when the intend is that it is left-rotated by 3 steps.
  5. Proof that the "Mix Column" step (to be read as MixColumns) is reversible, which is necessary for decryption to be possible, is alluded to only by dumping an alleged inverse of the polynomial used in MixColumns, without derivation.
  6. On closer inspection, the matrix given for MixColumns does not correspond to the polynomial stated for MixColumns per the conventions used in the real AES; and the alleged inverse polynomial can not match either, according to any convention, for it contains too many terms with multiplication by $\{01\}$, so that decryption using it won't work. I conjecture that this would-be inverse polynomial simply has its four terms of even degree taken from the polynomial used for AES's InvMixColumns (within a reflexion); and other terms set to $\{01\}$, because there are a lot of these in the direct polynomial.
  7. The number of rounds in the 512-bit AES variant is set to 10 with the sole justification that there are "ten AES rounds", without reference to which of the three AES ciphers that applies to.
  8. The round index is variably $I$ or $i$ including in the same equation.
  9. The first round constant probably has a typo.
  10. But there's no test vector to settle that.
  11. Performance is compared against AES-128, stated as encrypting "128 bytes" in "30-50 Seconds" on an unspecified platform; which (if we ignore the spurious capital S) is about $2^{26}$ times slower than routinely achieved by a single core of a modern CPU with AES-NI.
  12. The 512-bit AES variant is stated as encrypting the same "128 bytes" in "20-40 Seconds" yet has "230%" the throughput; this creatively redefines benchmarking.
  13. It is stated that the "Processor Required" is "Less" than for regular AES, with no attempt to evaluate the number of operations or memory accesses per byte encrypted; indeed this is about the same as in AES-128 for all steps except MixColumns, where there is significantly more work per byte (twice as many columns, each requiring multiplication by a matrix with twice as many raws and twice as many columns, thus about 8 times more work for 4 times as many bytes, thus about twice more work per byte; admittedly, the proportion of entries in the matrix that hold a $\{01\}$ is higher, but this only partially lowers that increase in work).
  14. Proceedings is spelled "Pro-ceding's".
  15. Several entries in the citations are to equally vacuous papers published in caricatures of scientific journals.
  16. Two citations ([1] and [11]) are to other papers about AES-512, yet are not mentioned in the Existing Work section.
  17. Citation [1] is a 2010 paper strikingly similar to the 2014 paper itself, including having nearly the same title ("Implemented" rather than "Implementation"), yet other authors (and even more mistakes and vacuity).
  18. Citation [11] was published in the proceedings of an IAS 2011 conference with enough relation to the IEEE to be on their website and use their logo (notice that this IAS stands for Information Assurance and Security, not IEEE's Industry Applications Society). A look at this online version shows it is strikingly similar to the 2014 article (including same erroneous polynomials, typo in first round constant, and 230% improvement), with different authors. I vote this 2011 paper as poor (especially on justification of security and misleading benchmark), but the least objectionable of the three.
  19. The numbers for references in the text are often from text cut and pasted from the 2010 paper, rather than related to the numbering of the references given in the end.
  20. The paper is published in a "peer reviewed" journal which most visible claim of seriousness is that used to be that it is an "ISO 3297:2007 Certified Organization". A cursory look at the summary of this standard shows that it is about numbering publications, not review of their content. Now that journal boasts an impact factor of 6.577; this is telling of how reliable a measure of seriousness the impact factor is.
$\endgroup$
  • 3
    $\begingroup$ The paper that you found is vacuous to the point of being funny. The reference to an "ISO 3297:2007 Certified Organization" should act as a snake-oil warning, for this standard only defines the numbering of publications. $\endgroup$ – fgrieu Nov 14 '14 at 18:20
  • 2
    $\begingroup$ It looks suspiciously like one of the earlier snake oil papers...same organization. Buy me a paper? $\endgroup$ – Maarten Bodewes Nov 15 '14 at 2:47
  • 2
    $\begingroup$ "since AES-128 is safe enough for anything foreseeable" ...except when the cryptosystem is re-keying sufficiently frequently for collisions in the key space to become a concern. $\endgroup$ – Henrick Hellström Nov 15 '14 at 8:25
  • 1
    $\begingroup$ I have edited the answer to tone down the appreciation of AES-128 security. Still, if we re-key AES-128 every millisecond for thirty years, that's less than $2^{40}$ keys, and odds of hitting the same key twice are less than $2^{-49}$, an acceptable risk. However, if the same known plaintext gets enciphered with every key (as in CTR mode with zero rather than random IV), odds of finding one of the key with $2^{80}$ encryptions and searches in 16TB of data are $2^{-7}$, slightly worrying. $\endgroup$ – fgrieu Nov 15 '14 at 11:44
  • 2
    $\begingroup$ remember there are potentially billions of devices using AES at the same time with different keys, and growing every year $\endgroup$ – Richie Frame Nov 17 '14 at 2:53
2
$\begingroup$

As mentioned in the answer by @fgrieu, AES is a standard (Advanced Encryption Standard) which is only defined for key sizes 128, 192 and 256. The actual underlying cryptographic algorithm is called Rijndael. At the time of its design (late 90s) key size of 256 bits was considered a huge enough security margin, while larger key sizes would increase computation complexity without providing much additional security.

As processors became more powerful and switched to 64-bit architecture the overhead of computing larger block sizes is not so significant anymore and some modern ciphers introduce 512-bit blocks. For example a cipher Kalyna chosen as Ukrainian National Encryption standard is based on Rijndael and has mode for 512-bit key size.

$\endgroup$
0
$\begingroup$

In fact we can, it is not common, because when NIST did choose AES candidates, they limit block size to 128 bit, and key to 128, 192, or 256 bits. For me this limitation is pure artificial and created just to make some sort of standard approach. We won't speculate on reason they decide to do so. In PHP for example you can specify block size as 256 bit, so I assume if you have enough knowledge, it's very possible to "unlock" higher key bit in code, or add necessary implementation

$\endgroup$
  • 4
    $\begingroup$ From the Rijndael proposal: "For Rijndael, the block length and the key length can be independently specified to any multiple of 32 bits, with a minimum of 128 bits, and a maximum of 256 bits" $\endgroup$ – Maarten Bodewes Nov 15 '14 at 2:51
  • $\begingroup$ Say we could implement AES 512 key size, how can we be sure that it is secure? you know, cryptography is a complex matter! $\endgroup$ – hamedb71 Nov 15 '14 at 6:11
  • $\begingroup$ This is like saying that Duplo being the largest version of Lego is arbitrary, and you should be able to keep scaling up — but Lego and Duplo are designed differently, if you actually look. Same goes for the different AES key-size variants. There is not some arbitrary limitation at 256. The larger variants would need to be expertly designed and evaluated. If you do that youself, and you're not a cryptologist, you're a fool. $\endgroup$ – ruief Oct 10 '16 at 15:41

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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