Decimal encryption

Hal Finney hal at
Wed Aug 27 18:46:14 EDT 2008

I wrote:
> Looking a little more closely, I found this paper by Patarin from
> Crypto 2005 which describes security bounds for higher round Feistel
> constructions:

I was wrong, this was from Crypto 03. And as Eric Rescorla has already
pointed out, Patarin had an improved the result the following year where
he showed that 6 rounds was sufficient for security.

Greg Rose wrote:
> >> So, you don't have a 133-bit block cipher lying around? No worries, I'll
> >> sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit
> >> block cipher like AES. To encrypt, do:
> >>
> >> 1. Encrypt the first 128 bits (ECB mode)
> >> 2. Encrypt the last 128 bits (also ECB mode).
> "Hal Finney" wrote:
> > I am not familiar with the security proof here, do you have a reference?
> > Or is it an exercise for the student?
> It's a degenerate case of Rivest's All-or-nothing transform (which 
> applies to larger, multi-block blocks, if you know what I mean :-) ). I 
> believe he gave a security proof, some 6ish years ago. But I could be 
> confabulating.

Hmmm, looking at Rivest's "package transform" which was his original
proposal for an AONT, that seems to be different and actually expanded
the message size. I haven't been able to find an AONT which is quite
like this.

One limitation with this proposal is that it appears that it will only
be as strong as the size of the overlapping region. However in this case
the overlap is 128-5 or 123 bits, so the birthday bound will be about
2^62 rather than the ideal 2^64, and that is hardly noticeable. So it
does seem like it could be a good choice here. Doing a little over 3 AES
encryptions will be much better than the 6 which seem to be necessary for
the Feistel approach. However such a substantial improvement certainly
makes a proof of security more interesting.

Hal Finney

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list