6 ms·
Don't pass on small block ciphers
- AlotOfReading 7mo agoI agree with the article, but I think it could go farther. Instead of having primitives for every 32/48/64/122 bit block, we need good format-preserving encryption. Then all of this advice boils down to "use as many bits as you need" and we can keep using the standard primitives with hardware support. If you need more security in the future, you only need to decrypt and reencrypt with the new size.
- bflesch 7mo agoAre you suggesting a very large custom blocksize? I don't think this would be feasible beyond a few megabytes.
- AlotOfReading 7mo agoNo, a FPE algorithm is a cryptographic construct that uses an existing block cipher (e.g. AES-256) to construct a cryptographically secure permutation of the input without length extension. That is, input size = output size, for all sizes. Ideally, if input size >= block size of the underlying cipher, the resulting permutation is no weaker than just using the cipher directly. You could use FPE for multi-megabyte permutations, but I don't know why you would.
- Dylan16807 7mo agoSmall sizes have to be used with extra care, so I wouldn't want to make a generic function for all sizes. For bigger sizes we already have nice functions that take care of everything.
- AlotOfReading 7mo agoThe article lays out exactly why you'd want small sizes, even with the risks. The good qualifier just means that it'd have to be no riskier than any other algorithm at the same length.
- Dylan16807 7mo agoI agree? That doesn't affect what I said. You shouldn't make a one-size-fits-all function that scales that small. It should have to be a deliberate choice to switch from normal mode to small mode, and anyone that hasn't looked into it deeper shouldn't even know about the small mode.
- AlotOfReading 7mo agoI suppose I don't understand your point. On one hand, you can have different algorithms for each of 32, 64, etc with potentially different pitfalls and usage requirements. On the other, you can have one algorithm that implements all of them. I wasn't trying to comment on how that should be exposed in the library (because crypto lib design is a whole 'nother topic), but I'm not opposed to it being explicit. Same as CRCs, really. You can easily write a function that performs CRCs of any size and expose different parameterizations as CRC-8/16/32/64 etc.
- Dylan16807 7mo agoI'm responding to the idea of "use as many bits as you need" by saying it could be reasonable for small encryption but it should be kept separate from normal encryption and not made into a general statement. Purely inside the realm of small lengths with deliberate tradeoffs I have no critique on your original statement, but I wanted to make clear that it should stay within that realm or it needs changes.
- PunchyHamster 7mo agoNowadays even many small microcontrollers get AES acceleration so I don't see much reason
- avidiax 7mo agoIf you want to encrypt a serial number, you don't want the output to be 256 bits.
- adrian_b 7mo agoThe size of encrypted data is completely independent of the block size of a block cipher function that is used for data encryption. Nowadays, there is almost never any reason to use for encryption any other modes of operation except CTR or OCB, which do not expand the size of encrypted data. That said, the parent article was less about encryption and more about random number generation, which is done by encrypting a counter value, but you never need to decrypt it again. In RNGs, the block size again does not matter, as the output can be truncated to any desired size.
- avidiax 7mo agoThe problem domain is that you want to separately encrypt/decrypt various 32-bit serial numbers. CTR mode turns this into just an XOR operation. That provides very little security. Anyone observing sequential sequence numbers (particularly rollovers) will quickly derive the partial value of the first CTR mode cipher block. A 32-bit cipher, on the other hand, essentially creates a permutation of the entire 32-bit space that's reversible with the key. Ideally, the encrypted value of serial #1 tells you nothing about the value of serial #2, which is the case for practical 32-bit ciphers.
- SAI_Peregrinus 7mo agoAES is most often used in a streaming mode, where it's used to generate a keystream. AES alone is useless, it MUST have a mode of operation to provide any security. A streaming mode can then encrypt any number of bits greater than 0. AES-CTR is one of the more common streaming modes.
- bflesch 7mo agoSlightly unrelated, but aren't these AES-specific custom CPU instructions just a way to easily collect the encryption keys? There is a speedup but is it worth the risks? If I were a nation state actor, I'd just store the encryption keys supplied to the AES CPU instruction somewhere and in case the data needs to be accessed you just read the stored keys. No need to waste time deploying a backdoored CPU firmware and wait for days or weeks, and then touch the hardware a second time to extract the information. When all AES encryption keys are already stored somewhere on the CPU, you can easily do a drive-by readout at any point in time. Linux kernel has a compile time flag to disable use of custom CPU instructions for encryption, but it can't be disabled at runtime. If "software encryption" is used, the nation state actor needs to physically access the device at least two times or use a network-based exploit which could be logged.
- Aachen 7mo agoI am not a chip designer but from my limited understanding, this "somewhere" is the problem. You can have secret memory somewhere that isn't noticed by analysts, but can it remain secret if it is as big as half the cpu? A quarter? How much storage can you fit in that die space? How many AES keys do you handle per day? Per hour of browsing HN with AES TLS ciphers? (Literally all supported ciphers by HN involve AES) We use memory-hard algorithms for password storage because memory is more expensive than compute. More specifically, it's die area that is costly, but at least the authors of Argon2 seem to equate the two. (If that's not correct, I based a stackoverflow post or two on that paper so please let me know.) It sounds to me like it's easily visible to a microscope when there's another storage area as large as the L1 cache (which can hold a few thousand keys at most... how to decide which ones to keep) Of course, the cpu is theoretically omnipotent within your hardware. It can read the RAM and see "ah, you're running pgp.exe, let me store this key", but then you could say the same for any key that your cpu handles (also rsa or anything not using special cpu instructions)
- bflesch 7mo agoGood points, but might be mitigated by knowing that the first key after boot is for HDD encryption and if storage is limited then keep counter for each key, and always overwrite least frequently observed key.
- doomrobo 7mo ago>Small block ciphers are thus generally a bad idea against active adversaries. >However, they can be very useful against passive adversaries whose capability is limited to observing identifiers, who are then unable to map them to the original value. Really? Isn’t the Sweet32[0] attack mostly passive? “We show that a network attacker who can monitor a long-lived Triple-DES HTTPS connection between a web browser and a website can recover secure HTTP cookies by capturing around 785 GB of traffic.” [0] https://sweet32.info/ https://sweet32.info/
- Joker_vD 7mo ago...a long-lived HTTPS connection that manages to transfer >700 GiB of traffic, with no disconnects, and presumably has re-keying disabled? An interesting theoretical setup, I guess.
- cyberax 7mo agoSmall block ciphers are great for some use-cases! 32-bit block ciphers are a good way to create short opaque IDs because they provide a bijection between two sets of integers. And even if your ID is slightly shorter than 32-bit you can easily shave off a few bits with cycle walking: https://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_cycle_walking https://en.wikipedia.org/wiki/Format-preserving_encryption#F... E.g. if you want to make sure your IDs can be mapped into 31/63 bits. I especially like the RC-5 cipher for these kinds of uses. It can be implemented in just a few lines of code and there are standard test vectors for it.
- jcalvinowens 7mo agoFunny your example is rc5, I wrote exactly what you describe to generate 32-bit cookies in a random prototype a few years ago: https://github.com/jcalvinowens/sdvr/blob/main/rc5.c https://github.com/jcalvinowens/sdvr/blob/main/rc5.c It is cute, but surely there's a more efficient way than RC5? There are bijective hash functions which are much cheaper (murmur, at least).
- cyberax 7mo agoIn my case, performance was utterly unimportant. But is Murmur actually bijective?
- jcalvinowens 7mo agoMine too, I was just curious. I recall empirically determining murmur was bijective across all 32-bit inputs, but I can't find that written down anywhere.
- adrian_b 7mo agoThe RC-5 cipher was very nice for its day, but I am certain that it is much slower than AES on any modern CPU, with the exception of microcontrollers, where nonetheless other solutions, e.g. ChaCha20, may be faster. AES also needs only a handful of lines of code for its implementation (using assembly). For such an application, you can even reduce the number of rounds of AES-128, e.g. from 10 to 4. When you want truly uniform random numbers, then encrypting with AES-128, then truncating, is best. If you want invertible encryption, then you should encrypt a counter and either use a 32-bit addition or a 32-bit XOR for encrypting the 32-bit number. With a single AES-128 invocation for generating a random mask, you can encrypt four 32-bit numbers. Of course, when speed does not matter, you can use pretty much any of the historical block ciphers, because the security requirements for encrypting 32-bit numbers are very low, since they are easier to find by brute force searching than by attempting to break any kind of encryption.
- whizzter 7mo agoNot a cryptographer but I'm not liking the "advice" of encrypting the first 64bits of the UUID. An user of an opensource application using this known "encryption" will be able to approximate the real UUID values based on creation time of objects they control and then would probably be able to approximate keys for 64bit encryption (although I guess one could design a cipher with a far larger key than block size, but it'd be a NIH design with all their pitfalls). But looking at it sanely, UUIDv7 isn't perfect and no reason really not to "encrypt" the entire UUID with AES instead (often built into hardware anyhow) instead of just the first part.
- FiloSottile 7mo agoAll of these small block ciphers have regularly large keys.
- mananaysiempre 7mo agoWhat symmetric cryptography is there that would be reasonable on a small 8-bitter? This means - As little code as possible; - As little constant data as possible; - Little to no shifts by amounts not divisible by 8, as there may not be a barrel shifter even for bytes; - No shifts by variable amounts, including as a space-saving technique, for the same reason; - No multiplies beyond 16×16 bits, and preferably none at all, as there may not be a multiplier. Speck, mentioned in TFA, fits this very well. None of the things that came out of eSTREAM or the NIST lightweight cryptography competition even qualify, as far as I can tell, as the “lightweight” part is very keen on things that are easy in hardware but hard (slow, space-hungry, or both) in software. Gimli exists but is kind of chonky. So is Speck truly it? Is just noöne interested in the problem?
- adrian_b 7mo agoChaCha20 satisfies your conditions. The only disadvantage of ChaCha20 vs. Speck is a bigger state, you need 128 bytes for it (64 bytes of state + 64 bytes for the intermediate computations), but that is not likely to be a problem, except in the smallest microcontrollers. The bigger state of ChaCha20 is determined by higher security requirements. The advantage of ChaCha20 is that it is supported by standard protocols, e.g. TLS 1.3 and SSH. The standard protocols mentioned above include ChaCha20 precisely for the case of communication with smaller or older CPUs, which do not have hardware AES support.
- mananaysiempre 7mo agoFor some reason (and despite remembering it being called an “add-rotate-XOR design”) I was sure that ChaCha20 used multiplies, even though of course it does not. Thank you for setting me straight on this. I’m not sure I’m all that optimistic about its code size—the standard C implementation with its eight inlined quarter-rounds seems certain to end up downright bloated compared to Speck—but I guess if I wasn’t picky about performance it could be boiled down to something reasonable. (Same for ASCON of eSTREAM & NIST LWC fame, which I also remembered being worse than it actually is.) Could be worth sitting down with an assembler at some point. There’s also the question of why you’d bother with an 8-bitter at all (for anything more substantial than a TV remote or a musical postcard) in a world where the CH32 exists. As for TLS or SSH, I’m not sure how much of a meaningful advantage it is. Talking to just about anything in the outside world likely excludes non-ephemeral TLS-PSK, which means that you’re going to need to implement a key exchange. And the code for that is likely to dwarf everything else, isn’t it?..
- tptacek 7mo agoA lot of the lightweight cipher justification in this post seems like it overlaps a lot with Format Preserving Cryptography, which uses (generally) more conventional symmetric primitives (16-byte-block ciphers, for instance) to handle encryption with small domains: https://eprint.iacr.org/2009/251.pdf https://eprint.iacr.org/2009/251.pdf
- throw0101c 7mo agoAny reason not to use Ascon, which not only got Official Status™ from NIST: * https://www.nist.gov/news-events/news/2023/02/nist-selects-lightweight-cryptography-algorithms-protect-small-devices https://www.nist.gov/news-events/news/2023/02/nist-selects-l... * https://csrc.nist.gov/pubs/sp/800/232/final https://csrc.nist.gov/pubs/sp/800/232/final But was also a lightweight finalist in CAESAR (along with ACORN): * https://en.wikipedia.org/wiki/CAESAR_Competition https://en.wikipedia.org/wiki/CAESAR_Competition * https://en.wikipedia.org/wiki/Ascon_(cipher) https://en.wikipedia.org/wiki/Ascon_(cipher)
- 201984 7mo agoAscon is a stream-oriented AEAD, not a block cipher, and it requires a nonce. Because of this, it would not work for the usecases in TFA, not to mention it's also quite a bit slower than Speck.