4 ms·

Bitslicing for Constant Time Cryptography (2020)

adg001 5y ago
Those of us interested in bitslicing may want to check out my – now 10 years old – pedagogical bitsliced implementation of the TEA block cipher. https://web.archive.org/web/20110813104823/http://plaintext.crypto.lo.gy/article/378/untwisted-bit-sliced-tea-time https://web.archive.org/web/20110813104823/http://plaintext.... Code here: https://github.com/secYOUre/bstea https://github.com/secYOUre/bstea
anonymousDan 5y ago
Anyone know of equivalent bitsliced MAC/cryptographic hash algorithms (or resources describing how that might work)? Also, am I right in saying the implementations described in the article are effectively 'CPU only', i.e. no memory accesses are performed beyond the initial loading of the input data into registers and writing the final result?
- tatersolid 5y ago
  Most current cryptographic hash functions have no lookup tables, multiplies, or other data dependencies and are constant time even when used with a secret key as in HMAC. Obviously variable input length varies run time as with all symmetric crypto. See the end of this long Stack Exchange answer by a well-regarded cryptography implementer: https://crypto.stackexchange.com/a/11305/8925 https://crypto.stackexchange.com/a/11305/8925
jedisct1 5y ago
Fixslicing is a slightly different technique that is a little bit faster: https://eprint.iacr.org/2020/1123.pdf https://eprint.iacr.org/2020/1123.pdf Bitsliced/fixsliced AES remains painfully slow compared to lookup-based AES, but also to ciphers that can easily be implemented without side channels to start with. So, my recommendation would be: - Do you have hardware-accelerated, side-channels free AES? Go use it. - Are side channels part of your threat model? Do you think they are practical in the context of your application? (for the vast majority of cases, the honest answer is: they aren't) If this is the case, do NOT use AES or anything that would require bitslicing/fixslicing to be safe. ChaCha20 is likely to perform way better on that platform. Not to mention more recent alternatives. - They are not? For some reason, you still want to use AES? Use a table-based implementation and don't worry about it. Yes, this is fine. Don't take it the wrong way. Bitslicing/fixslicing are excellent mitigation against side channels. But AES+bitslicing shouldn't be your go to choice.
ncmncm 5y ago
I think it was Emilia Käsper who was the first to do this. That was back when we didn't have any built-in AES instructions.

Those of us interested in bitslicing may want to check out my – now 10 years old – pedagogical bitsliced implementation of the TEA block cipher. https://web.archive.org/web/20110813104823/http://plaintext.crypto.lo.gy/article/378/untwisted-bit-sliced-tea-time https://web.archive.org/web/20110813104823/http://plaintext.... Code here: https://github.com/secYOUre/bstea https://github.com/secYOUre/bstea

anonymousDan 5y ago

Anyone know of equivalent bitsliced MAC/cryptographic hash algorithms (or resources describing how that might work)? Also, am I right in saying the implementations described in the article are effectively 'CPU only', i.e. no memory accesses are performed beyond the initial loading of the input data into registers and writing the final result?

tatersolid 5y ago
Most current cryptographic hash functions have no lookup tables, multiplies, or other data dependencies and are constant time even when used with a secret key as in HMAC. Obviously variable input length varies run time as with all symmetric crypto. See the end of this long Stack Exchange answer by a well-regarded cryptography implementer: https://crypto.stackexchange.com/a/11305/8925 https://crypto.stackexchange.com/a/11305/8925

jedisct1 5y ago

Fixslicing is a slightly different technique that is a little bit faster: https://eprint.iacr.org/2020/1123.pdf https://eprint.iacr.org/2020/1123.pdf Bitsliced/fixsliced AES remains painfully slow compared to lookup-based AES, but also to ciphers that can easily be implemented without side channels to start with. So, my recommendation would be: - Do you have hardware-accelerated, side-channels free AES? Go use it. - Are side channels part of your threat model? Do you think they are practical in the context of your application? (for the vast majority of cases, the honest answer is: they aren't) If this is the case, do NOT use AES or anything that would require bitslicing/fixslicing to be safe. ChaCha20 is likely to perform way better on that platform. Not to mention more recent alternatives. - They are not? For some reason, you still want to use AES? Use a table-based implementation and don't worry about it. Yes, this is fine. Don't take it the wrong way. Bitslicing/fixslicing are excellent mitigation against side channels. But AES+bitslicing shouldn't be your go to choice.

ncmncm 5y ago

I think it was Emilia Käsper who was the first to do this. That was back when we didn't have any built-in AES instructions.