Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Don't pass on small block ciphers

00f.net

Post reply on HN
Print view View original

31–40 of 64 posts

Re: Don't pass on small block ciphers

#31

Post by cyberax »

jcalvinowens wrote: post #19
cyberax wrote: post #12

Small 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#F... E.g. if you want to make sure your IDs can be mapped into 31/63 bits. I…

Funny 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 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).

In my case, performance was utterly unimportant.

But is Murmur actually bijective?

Re: Don't pass on small block ciphers

#32

Post by fluoridation »

201984 wrote: post #27
fluoridation wrote: post #13

Earlier quoted context omitted.

In that case just use CTR mode, no?

In the context of encrypting 32 or 64 bit IDs, where there is no nonce, that'd be equivalent to XOR encryption and much weaker than TFA's small block ciphers.

Would it, though? Either way you're operating in ECB mode with 2^32 or 2^64 values. Why is one more secure than the other?

EDIT: What I mean is you can do cypher = truncate(plain ^ AES(zero_extend(plain))).

Re: Don't pass on small block ciphers

#33

Post by tptacek »

A 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

Re: Don't pass on small block ciphers

#34

Post by 201984 »

adrian_b wrote: post #29
201984 wrote: post #27

Earlier quoted context omitted.

In the context of encrypting 32 or 64 bit IDs, where there is no nonce, that'd be equivalent to XOR encryption and much weaker than TFA's small block ciphers.

If you really want to encrypt and decrypt 32-bit numbers without having any nonces available, the fastest way on non-microcontroller CPUs remains using the AES instructions. 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 ca…

Are you certain using AES is still faster? Let's say for a 32-bit block size and 64-bit key.

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.

Re: Don't pass on small block ciphers

#35

Post by tptacek »

fluoridation wrote: post #13
chowells wrote: post #5

Earlier quoted context omitted.

Basically all of the use cases in the article don't make sense with AES. That's not because it's AES. That's because its blocks are significantly larger than the data you want to protect. That's the point the article was making: in very specific circumstances, there is practical value in having the cipher output be small.

In that case just use CTR mode, no?

https://www.cs.ucdavis.edu/~rogaway/papers/thorp.pdf

(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).

Re: Don't pass on small block ciphers

#36

Post by 201984 »

fluoridation wrote: post #32
201984 wrote: post #27

Earlier quoted context omitted.

In the context of encrypting 32 or 64 bit IDs, where there is no nonce, that'd be equivalent to XOR encryption and much weaker than TFA's small block ciphers.

Would it, though? Either way you're operating in ECB mode with 2^32 or 2^64 values. Why is one more secure than the other? EDIT: What I mean is you can do cypher = truncate(plain ^ AES(zero_extend(plain))).

>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)
And in this case, since AES(key) does not depend on the plaintext, it would just be XOR by a constant.

Re: Don't pass on small block ciphers

#37

Post by tptacek »

cyberax wrote: post #30
adrian_b wrote: post #26

Earlier quoted context omitted.

The 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…

The problem is that AES needs a 128-bit block. 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…

Right, but balanced and unbalanced Feistel networks let you turn the 16-byte AES block into an arbitrarily small PRF.

Re: Don't pass on small block ciphers

#38

Post by jcalvinowens »

cyberax wrote: post #31
jcalvinowens wrote: post #19

Earlier quoted context omitted.

Funny 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 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).

In my case, performance was utterly unimportant. But is Murmur actually bijective?

Mine 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.

Re: Don't pass on small block ciphers

#39

Post by cyberax »

tptacek wrote: post #37
cyberax wrote: post #30

Earlier quoted context omitted.

The problem is that AES needs a 128-bit block. 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…

Right, but balanced and unbalanced Feistel networks let you turn the 16-byte AES block into an arbitrarily small PRF.

Well, yes. But at this point you're just making a new cipher with AES as the round function. And I think it should be at least as safe as the round function?

I have not checked lately, but is it actually the recommendation for format-preserving encryption?

Re: Don't pass on small block ciphers

#40

Post by botusaurus »

201984 wrote: post #34
adrian_b wrote: post #29

Earlier quoted context omitted.

If you really want to encrypt and decrypt 32-bit numbers without having any nonces available, the fastest way on non-microcontroller CPUs remains using the AES instructions. 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 ca…

Are you certain using AES is still faster? Let's say for a 32-bit block size and 64-bit key. 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+a…

maybe the reason they are so close is that the AES microcode is inplementing exactly those operations
Post reply on HN