3 ms·

It's much more interesting to implement AES without the table lookups-- as doing so requires constructing a boolean circuit that computes the same result as the

by nullc 4y ago

It's much more interesting to implement AES without the table lookups-- as doing so requires constructing a boolean circuit that computes the same result as the tables, more useful too since the table lookups result in security killing side channels. :) The author might be surprised at how often someone's random "learn 2 crypto" ends up in use in production. Kudos for the warnings, though I doubt that actually accomplish much: People copying and pasting code usually have tremendous tunnel vision.

charlieyu1 4y ago
Isn't table lookup constant time?
- deleted 4y ago
  [deleted]
- dchest 4y ago
  These are called "cache-timing attacks". In presence of caches, no memory lookup can be guaranteed to be constant time. Any memory lookups that use secret indices are thus not timing-safe, however non-secret indices are OK. See https://cr.yp.to/antiforgery/cachetiming-20050414.pdf https://cr.yp.to/antiforgery/cachetiming-20050414.pdf Here's an implementation that doesn't use tables: https://github.com/openbsd/src/blob/master/sys/crypto/aes.c https://github.com/openbsd/src/blob/master/sys/crypto/aes.c
  - mananaysiempre 4y ago
    (That implementation comes from BearSSL, whose website also has a discussion of the issue and a performance comparison[1].) [1] https://www.bearssl.org/constanttime.html https://www.bearssl.org/constanttime.html
- zgs 4y ago
  No. At least not with modern caching (or very old page boundary crossings). A constant time implementation has to avoid tables & compute the values directly (and slowly) or take special care to ensure that all of the table is hit/cached on each access.
  - nullc 4y ago
    > or take special care to ensure that all of the table is hit/cached on each access. For example, by using an oblivious read: Access each row, AND it with a mask that is either all 1s or all 0s depending on if its the row you want (which you must set without branching) and OR all the results together. Very slow.
fstokesman 4y ago
If someone copy-pastes this code in spite of the warnings, I consider them to be very much in own-risk territory. Sucks if they end up getting burned, but I don't consider myself responsible.
Retr0id 4y ago
Further, you can compute the whole block transform as a giant boolean circuit (aka bitslicing). This has various advantages, sidechannel resistence being one, but surprisingly it outperforms a more traditional implementation in many circumstances (e.g. in pure-python implementations: https://github.com/DavidBuchanan314/python-bitsliced-aes https://github.com/DavidBuchanan314/python-bitsliced-aes )

by nullc 4y ago

charlieyu1 4y ago

Isn't table lookup constant time?

deleted 4y ago
[deleted]
dchest 4y ago
These are called "cache-timing attacks". In presence of caches, no memory lookup can be guaranteed to be constant time. Any memory lookups that use secret indices are thus not timing-safe, however non-secret indices are OK. See https://cr.yp.to/antiforgery/cachetiming-20050414.pdf https://cr.yp.to/antiforgery/cachetiming-20050414.pdf Here's an implementation that doesn't use tables: https://github.com/openbsd/src/blob/master/sys/crypto/aes.c https://github.com/openbsd/src/blob/master/sys/crypto/aes.c
- mananaysiempre 4y ago
  (That implementation comes from BearSSL, whose website also has a discussion of the issue and a performance comparison[1].) [1] https://www.bearssl.org/constanttime.html https://www.bearssl.org/constanttime.html
zgs 4y ago
No. At least not with modern caching (or very old page boundary crossings). A constant time implementation has to avoid tables & compute the values directly (and slowly) or take special care to ensure that all of the table is hit/cached on each access.
- nullc 4y ago
  > or take special care to ensure that all of the table is hit/cached on each access. For example, by using an oblivious read: Access each row, AND it with a mask that is either all 1s or all 0s depending on if its the row you want (which you must set without branching) and OR all the results together. Very slow.

fstokesman 4y ago

If someone copy-pastes this code in spite of the warnings, I consider them to be very much in own-risk territory. Sucks if they end up getting burned, but I don't consider myself responsible.

Retr0id 4y ago

Further, you can compute the whole block transform as a giant boolean circuit (aka bitslicing). This has various advantages, sidechannel resistence being one, but surprisingly it outperforms a more traditional implementation in many circumstances (e.g. in pure-python implementations: https://github.com/DavidBuchanan314/python-bitsliced-aes https://github.com/DavidBuchanan314/python-bitsliced-aes )