Don't pass on small block ciphers(00f.net) |
Don't pass on small block ciphers(00f.net) |
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#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.
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.
Imagine that you want to obfuscate your order numbers in the database so that customers can't infer the volume of business by checking the order number.
You can use UUIDs, but you also want to keep the numbers short so they can be dictated over the phone. You can use random IDs, but then you need to lock them in the database during the object creation otherwise you might get collisions.
Or perhaps you have a distributed system and want to allocate a bunch of IDs for each node in advance.
RC-5 with its small block size neatly solves this. You can have a strictly increasing database sequence, and then just give out each node a bunch of numbers ("from 100 to 120"), and nodes can then generate IDs based on them. And there can be no collisions with other nodes because symmetric ciphers are obviously bijective.
For these kinds of use-cases performance is not an issue.
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).
But is Murmur actually bijective?
- 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?
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.
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?..
You could use FPE for multi-megabyte permutations, but I don't know why you would.
* https://www.nist.gov/news-events/news/2023/02/nist-selects-l...
* https://csrc.nist.gov/pubs/sp/800/232/final
But was also a lightweight finalist in CAESAR (along with ACORN):
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.
>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.”
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.
Moreover, cryptography has many applications, but the most important 3 of them are data encryption, data integrity verification and random number generation.
The optimal use of a cryptographic component, like a block cipher, depends on the intended application.
If you want e.g. 32-bit random numbers, the fastest method on either Intel/AMD x84-64 CPUs or Arm Aarch64 CPUs is to use the 128-bit AES to encrypt a counter value and then truncate its output to 32 bits. The counter that is the input to AES may be initialized with an arbitrary value, e.g. 0 or the current time, and then you may increment only a 32-bit part of it, if you desire so. Similarly for other sizes of random numbers that are less than 128 bit, you just truncate the output to the desired size. You can also produce random numbers that need to have 1 of a certain number of values that is different from a power of two, by combining either multiplication or division of the output value with rejection done either before or after the operation (for removing the bias).
Similarly, for message authentication, if you have some method that produces an 128-bit MAC, it can be truncated to whatever value you believe to be a good compromise between forgery resistance and message length.
For encryption, short data must be encrypted using either the CTR mode of operation or the OCB mode of operation (where only the last incomplete data block is encrypted using the CTR mode). With these modes of operation, the encrypted data can have any length, even a length that is not an integer number of bytes, without any length expansion of the encrypted message.
The advice given in the parent article is not bad, but it makes sense only in 32-bit microcontrollers, because since 2010 for x86-64 and since 2012 for Aarch64 any decent CPU has AES instructions that are much faster than the implementation in software of any other kind of block cipher.
Moreover, for random number generation or for data integrity verification or for authentication, there are alternative methods that do not use a block cipher but they use a wider invertible function, and which may be more efficient, especially in microcontrollers. For instance, for generating 128-bit unpredictable random numbers, you can use a counter with either an 128-bit block cipher function together with a secret key, or with a 256-bit invertible mixing function, where its 128-bit output value is obtained either by truncation or by summing the 2 halves. In the first case the unpredictability is caused by the secret key, while in the second case the unpredictability is caused by the secret state of the counter, which cannot be recovered by observing the reduced-size output.
For applications where a high level of security is not necessary, e.g. for generating 32-bit random numbers, the already high speed of AES-128 (less than 0.5 clock cycles per output byte on recent CPUs) can be increased by reducing the number of AES rounds, e.g. from 10 to 4, with a proportional increase in throughput.
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.
Out of all micro controllers I've worked with, only a single one had AES cpu instructions.
The storage required for this would be humongous and the CPU cannot know for which data the keys have been used. Moreover this would too easily be defeated, because even if the AES instructions allow to specify a derived round key in them, you can always decline to do this and use a separate XOR instruction for combining the round keys with the intermediate states. Detecting such a use would be too difficult.
No, there is no base for fearing that the AES keys can be stored in CPUs (on the other hand you should fear that if you store keys in a TPM, they might never be erased, even if you demand this). The greatest possible danger of adversarial behavior of a CPU exists in the laptop CPUs with integrated WiFi interfaces made by Intel. Unless you disconnect the WiFi antennas, it is impossible to be certain that the remote management feature of the WiFi interface is really disabled, preventing an attacker to take control of the laptop in a manner that cannot be detected by the operating system. The next danger by importance is in the computers that have Ethernet interfaces with the ability to do remote management, where again it is impossible to be certain that this feature is disabled. (A workaround for the case when you connect such a computer to an untrusted network, e.g. directly to the Internet, is to use a USB Ethernet interface.)
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)
I recall empirically determining murmur was bijective across all 32-bit inputs, but I can't find that written down anywhere.
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.
Like, I do take your point but it does seem quite involved for the chance that it'll get them something useful, and they still need to gain physical access to the intact device, and trust that it never gets out or the chipmaker's reputation is instantly trash and potentially bankrupt. And we know from Snowden documents that, at least in ~2013 (when aes extensions weren't new, afaik), they couldn't decrypt certain ciphers which is sorta conspicuous if we have these suspicions. It's a legit concern or thing to consider, but perhaps not for the average use-case
edit: nvm it was proposed in 2008, so that it didn't show up yet in ~2013 publications is not too surprising. Might still be a general point about that 'they' haven't (or hadn't) infiltrated most cpus in general
- 2004: Linux LUKS disk encryption [0]
- 2008: ring −3 / intel management engine [1]
- 2010: AES instruction set [2]
- 2009: TPM [3]
[0] https://en.wikipedia.org/wiki/Linux_Unified_Key_Setup
[1] https://en.wikipedia.org/wiki/Intel_Management_Engine
The CPU firmware blobs are encrypted and nobody except Intel can see what is running there. A handful of people on the planet have the tools and skills to analyze the chip for backdoors.
A small section of CPU cache could stay powered even though the OS is shut down, persisting the keys that were passed to the AES CPU instruction. As CPU is directly linked to wifi/bluetooth and USB chipsets, exfiltration could be possible both wirelessly and via special USB payload.
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.
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.
However, the AES mixing function is made from a 32-bit mixing function that is extended to blocks whose lengths are multiples of 32-bit by composing it with a byte permutation.
The standard byte permutation extends the block size from 32-bit to 128-bit, but with the current AES instructions of CPUs you can either cancel the byte permutation to get a 32-bit block size or you can replace it with a non-standard byte permutation, to get any block size that is a multiple of 32-bit.
If you cancel the byte permutation, four 32-bit words are encrypted independently, instead of one 128-bit block. This doubles the number of instructions, but this does not necessarily reduce the throughput, as the instructions may be executed concurrently, so the throughput measured in encrypted numbers will increase by a number between 2 and 4, depending on the CPU.
I have not checked lately, but is it actually the recommendation for format-preserving encryption?
I'll say I'm more comfortable using a straightforward FPE block cipher mode with AES than I am repurposing a weaker lightweight cipher to take advantage of its 32-bit block size.
I used the RC-5 cipher around 2015 to do that ID generation trick (and it's still in place in AWS as I can see), and there was no NIST standard back then. It also was not a really sensitive application, we just wanted to make IDs opaque.
You can exploit the fact that the core of AES consists of 32-bit invertible mixing functions. In order to extend AES to 128-bit, a byte permutation is used, which mixes the bytes of the 32-bit words.
The AES instructions are such, that you can cancel the byte permutation. In this case, you can use the AES instructions to encrypt separately four 32-bit words, instead of one 128-bit block.
Similarly by canceling the standard byte permutation and replacing it with separate permutations on the 2 halves, you can make the AES instructions independently encrypt two 64-bit words.
These AES modifications remain faster than any software cipher.
How to cancel the internal permutation and replace it with external shuffle instructions was already described in the Intel white paper published in 2010, at the launch of Westmere, the first CPU with AES instructions.
From https://en.wikipedia.org/wiki/Speck_(cipher), that Speck combination would use 22 rounds, and using the instruction timings for Zen 5 from https://instlatx64.github.io/InstLatx64/AuthenticAMD/Authent..., it looks like each round would take at most 3 cycles. (Dependency chain for each round is 3 instructions long, ror+add+xor). 22*3 = ~66 cycles.
Using AES with a pshufb to take out the ShiftRows step would be 2 cycles for the pshufb and 4 cycles for each aesenc, and at 10 rounds, you have ~60 cycles.
It's quite close, and to say which one wins, we'd need to actually benchmark it. One is not clearly much faster than the other.
EDIT: What I mean is you can do cypher = truncate(plain ^ AES(zero_extend(plain))).
How would you decrypt that though? You truncated 3/4ths of the AES output needed to decrypt it.
I thought you were suggesting this:
ciphertext = truncate(AES(key) ^ plaintext)
(Not that this is the only solution but that it motivates the problem of why you can't just naively apply AES to the problem).
If uniqueness is needed for a 32-bit number or a 64-bit number, then in AES-128 the byte permutation can be modified, to reduce the block size accordingly.
For the other examples with record identifiers, I am not sure whether the author meant for them to ever be decrypted. If decryption was intended, I disagree that this is the right solution. If an opaque record identifier is desired, it should be an unpredictable random number, which can be generated at maximum speed with AES. There is no need to ever decrypt such an identifier.
If other private information is needed, like a record counter, it should be put in separate fields, that are not provided to external entities, instead of encrypting it inside the identifier. Encrypting such private information would prevent its use in indexing anyway.
AES-128 can be easily modified to independently encrypting four 32-bit words per execution, instead of one 128-bit block, by cancelling the byte permutation that extends the AES mixing function from 32-bit to 128-bit. this would increase the throughput at least twice, depending on whether PSHUFB is done concurrently or not.
You have given the latencies of the instructions, not their throughput. When you use AES in such a way that you are limited by latency, that is normally wrong. The cryptographic libraries have multi-buffer functions, which compute e.g. 8 AES values, so that they are not limited by latencies.
Regarding the parent article, if you want an unpredictable identifier for a record, you should not do this by encrypting some value with the intent of decrypting it in the future. Instead of this, you should use as identifier an unpredictable random number. Such identifiers can be generated with AES in batches, at maximum throughput, and stored until they are needed for assignment to a record.
If you need in your record some information like time of creation or a monotonically increasing number, which you consider private, such information should be put in distinct fields, that you do not give externally, instead of attempting to encrypt them in a record identifier, which would need to be decrypted to access such information.
I did that because TFA is talking about encrypting 32 bit IDs, which is 1/4th of an AES block. There aren't multiple blocks to do at once in this scenario, and throughput numbers do not apply because each instruction depends on the result of the one before.
You mention doing multiple IDs at once, but the overhead of pulling multiple IDs into a single batch from something akin to URLs in web requests is likely gonna be worse than any gains.
>Instead of this, you should use as identifier an unpredictable random number. Such identifiers can be generated with AES in batches, at maximum throughput, and stored until they are needed for assignment to a record.
Now you lose the ability to sort the records in a database, and I fail to see what AES gives you here over any other random number generator.