Rendered at 09:38:30 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
benlivengood 12 hours ago [-]
Hey, one of my university professors! GF2^8 is also great for RAID6+ and Reed Solomon codes.
Back in the day it was tractable to build AES lookup tables for computing MixColumns and SubBytes similar to the site's multiplication table. Then djb found a remote timing attack, so processors started implementing hardware AES instructions.
_peeley 12 hours ago [-]
I was also pleasantly surprised to see a `uaf.edu` link on the front page of HN, and even more so when I saw it was written by Dr. Lawlor. His course on x86 assembly is easily one of the best classes I took in college.
mmozeiko 12 hours ago [-]
> Inverses exist for each operation, which makes decryption possible.
It is worth mentioning that in modern AES usage this feature does not really matter, because block cipher is used in CTR mode. In CTR block cipher is used to create long keystream bytes (pretty much one-time-pad key). This keystream gets xor'ed with plaintext to get ciphertext. Then getting from ciphertext back to plaintext is exactly the same xor operation with same keystream, no inverse AES operations needed.
adrian_b 1 hours ago [-]
There are better modes of operation than CTR, which have not been used due to a historical accident of being covered by a lot of patents, most of which were invalid or irrelevant, but nobody wanted to risk litigation.
The current dominant AES-GCM mode of operation is the consequence of the broken US IP laws and its supremacy is not determined by technical reasons.
That said, for Internet communication AES-GCM is sufficiently close to the optimum that there is no need to replace it (by sufficiently close I mean that its speed is only very slightly slower and the probability of not detecting forgeries is only very slightly higher).
However, the better modes of operation require the inverse of the block cipher function.
Nonetheless, if one wants an even better security and the block size is extended to 256 bits, due to another historical accident, the definition of the Intel and ARM AES instructions is such that for extended block sizes the decryption would be slower than encryption (the reason is that the decryption instructions are not the inverses of the encryption instructions, as they should have been).
This misfeature can be avoided by not using the decryption instructions, which is possible if the block size is not extended as in the original AES definition, but by using a Feistel structure where the 128-bit AES instructions modify alternatively the 2 halves of a block.
So it is possible to implement both the direct and the inverse form of a 256-bit block cipher function, with equal throughputs, by using only the encryption AES instructions. Such a 256-bit block cipher function can be used in any mode of operation, including in those that require its inverse.
orlp 12 hours ago [-]
AES is used for a whole lot more than just encryption in CTR mode.
pugfugly 9 hours ago [-]
No, it isn't. AES-CTR, AES-GCM, AES-CTR-DRBG is basically all AES is used for. Maybe if FAEST is standardized?
adrian_b 54 minutes ago [-]
That is correct for communication over the public Internet, which is dominated by standards like TLS and SSH.
Encryption is also used for other purposes, e.g. communication between private devices or data storage, for which other modes of operation have significant advantages.
bri3d 7 hours ago [-]
AES-CBC is unbelievably popular and relies on the AES inverse block cipher?
adgjlsfhk1 5 hours ago [-]
CBC historically was the most popular, but modern applications mostly use GCM which is counter mode. Block mode is too easy to get wrong, and doing it right is ~2x more expensive and less paralellizable.
adrian_b 32 minutes ago [-]
CBC in its standard form is not parallelizable at all. However, like for hashes, one could decompose the data in several parallel streams that are encrypted independently with CBC, for multiplying the speed.
CBC with a block cipher has been completely obsolete for decades, even if the huge inertia of cryptography software development has kept it in use in many places, even until today.
However, CBC has a descendant that is still useful. CBC is a derivative of CFB, from which it differs only in the place from which the output is extracted from the encryption automaton.
There is another derivative of CFB, where the block cipher function with a secret key is replaced by a wider bijective mixing function, where the output is extracted by truncation. Here the role of the secret key is played by the part of the state that is not extracted in the output and the encryption automaton obtained thus is equivalent with a CFB mode for a block cipher where the key would be changed after each block. The fact that no 2 blocks are encrypted with the same key eliminates all security problems of the traditional CBC/CFB.
Only the fact that encryption and decryption are not parallelizable is a disadvantage, but this is partially mitigated because integrity verification is a byproduct that is provided without additional expenses (by extending the string to be encrypted with a block of known content).
This mode of operation is what the team Guido Bertoni, Joan Daemen, Gilles Van Assche and Michaël Peeters has called "duplex encryption for sponge functions".
While that team has contributed many important things to the progress of cryptography, I hate that they have always coined a great number of new names for old things, and always without mentioning at all the correspondence between their new names and the old concepts that had been used for decades before them.
Their initial contributions from 2007 to 2012 were all about what is obtained when in all those of the classic modes of operation that were known by 1980 in which the inverse of the block cipher is not needed, one substitutes the block cipher with a truncated wide mixing function (in the Shannon sense), but for all of those they have invented new fancy names, like "sponge absorbing" (derived from CFB-MAC), "sponge squeezing" (derived from OFB), "donkeySponge" (derived from the Alred optimization of CBC-MAC) and the like.
ceroxylon 12 hours ago [-]
>Weirdly, members of a field of size pn are equivalent to polynomials of degree up to n
Wouldn't it be equivalent to polynomials of degree less than n (up to n−1)?
prideout 12 hours ago [-]
Is this post popular because of a recent mathematical discovery in this problem space?
dboreham 15 hours ago [-]
I don't know that "Weirdly" is right for the polynomial equivalence -- isn't that what Galois was trying to do in the first place (prove things about polynomials such as the impossibility of analytic solutions to higher order polynomials, and the impossibility of constructing a heptagon)?
tomsmeding 13 hours ago [-]
I read the "weirdly" as "unexpectedly", i.e. "you might not see this coming, but it's still true (and there's deep theory behind it)".
bananaflag 14 hours ago [-]
A bit, yeah. I deleted a comment where I said it's not quite the same but it kinda is, and figuring it out is very rewarding.
Back in the day it was tractable to build AES lookup tables for computing MixColumns and SubBytes similar to the site's multiplication table. Then djb found a remote timing attack, so processors started implementing hardware AES instructions.
It is worth mentioning that in modern AES usage this feature does not really matter, because block cipher is used in CTR mode. In CTR block cipher is used to create long keystream bytes (pretty much one-time-pad key). This keystream gets xor'ed with plaintext to get ciphertext. Then getting from ciphertext back to plaintext is exactly the same xor operation with same keystream, no inverse AES operations needed.
The current dominant AES-GCM mode of operation is the consequence of the broken US IP laws and its supremacy is not determined by technical reasons.
That said, for Internet communication AES-GCM is sufficiently close to the optimum that there is no need to replace it (by sufficiently close I mean that its speed is only very slightly slower and the probability of not detecting forgeries is only very slightly higher).
However, the better modes of operation require the inverse of the block cipher function.
Nonetheless, if one wants an even better security and the block size is extended to 256 bits, due to another historical accident, the definition of the Intel and ARM AES instructions is such that for extended block sizes the decryption would be slower than encryption (the reason is that the decryption instructions are not the inverses of the encryption instructions, as they should have been).
This misfeature can be avoided by not using the decryption instructions, which is possible if the block size is not extended as in the original AES definition, but by using a Feistel structure where the 128-bit AES instructions modify alternatively the 2 halves of a block.
So it is possible to implement both the direct and the inverse form of a 256-bit block cipher function, with equal throughputs, by using only the encryption AES instructions. Such a 256-bit block cipher function can be used in any mode of operation, including in those that require its inverse.
Encryption is also used for other purposes, e.g. communication between private devices or data storage, for which other modes of operation have significant advantages.
CBC with a block cipher has been completely obsolete for decades, even if the huge inertia of cryptography software development has kept it in use in many places, even until today.
However, CBC has a descendant that is still useful. CBC is a derivative of CFB, from which it differs only in the place from which the output is extracted from the encryption automaton.
There is another derivative of CFB, where the block cipher function with a secret key is replaced by a wider bijective mixing function, where the output is extracted by truncation. Here the role of the secret key is played by the part of the state that is not extracted in the output and the encryption automaton obtained thus is equivalent with a CFB mode for a block cipher where the key would be changed after each block. The fact that no 2 blocks are encrypted with the same key eliminates all security problems of the traditional CBC/CFB.
Only the fact that encryption and decryption are not parallelizable is a disadvantage, but this is partially mitigated because integrity verification is a byproduct that is provided without additional expenses (by extending the string to be encrypted with a block of known content).
This mode of operation is what the team Guido Bertoni, Joan Daemen, Gilles Van Assche and Michaël Peeters has called "duplex encryption for sponge functions".
While that team has contributed many important things to the progress of cryptography, I hate that they have always coined a great number of new names for old things, and always without mentioning at all the correspondence between their new names and the old concepts that had been used for decades before them.
Their initial contributions from 2007 to 2012 were all about what is obtained when in all those of the classic modes of operation that were known by 1980 in which the inverse of the block cipher is not needed, one substitutes the block cipher with a truncated wide mixing function (in the Shannon sense), but for all of those they have invented new fancy names, like "sponge absorbing" (derived from CFB-MAC), "sponge squeezing" (derived from OFB), "donkeySponge" (derived from the Alred optimization of CBC-MAC) and the like.
Wouldn't it be equivalent to polynomials of degree less than n (up to n−1)?