[Cryptography] [cryptography] NIST Workshop on Elliptic Curve Cryptography Standards

[Ray Dillinger]

On 05/13/2015 01:46 PM, dj at deadhat.com wrote:
> Bear wrote:
>> How about "The block size is exactly the same as the message
>> size no matter what the message size happens to be?"

>> No block boundaries inside the message, and every bit of the
>> ciphertext depending on every bit of the plaintext, means
>> entire classes of attacks just don't have anything to work
>> with.
> 
> I would like such a thing to exist. Do you have an algorithm handy? The
> closest thing I can think of is format preserving encryption, like
> Rogaway's Sometimes Recurse Shuffle. That can work on arbitrary string
> sizes.

I can think of a few ways to do it that would work and be secure,
but all are too heavy for anything that's supposed to compete with
well-studied ciphers on the basis of speed or gate count.  Here's
the top two in my opinion.


Option 1: A well-studied fast cipher like AES or something, used
twice in CBC mode:  Once from front to back, and then from back
to front at an offset of half the block size. So the second time
through, you start at the tail end and each block you encrypt is
half of two different first-round blocks.  This has the advantage
of being much more conservative design built on the security of
something that's already well studied, and "only" takes twice as
much time as that thing.  The end result is that every bit of the
output depends on every bit of the input.  If you insert
an additional block encryption with a customized amount of
overlap to make it come out even, you get ciphertexts exactly
the same size as plaintexts.



Option 2: A block-ish (one-block) cipher with multiple layers
of S-boxes and between them P-boxes calculated from message
size to achieve complete diffusion as rapidly as possible.
I actually prefer this option from an aesthetic point of
view, but it's got a lot of security questions.

Each layer of S-boxes could increase the amount of diffusion
by a factor of the size of the S-box in bits, so with 8-bit
S-boxes, one layer gives diffusion over 8 bits, 2 over 64 bits,
3 over 512 bits, 4 over 4096 bits, etc.  And to get Feistel's
security properties you'd want at least four times the number
of layers required for full diffusion.

But finding S-Boxes that are secure given any set of P-boxes
computed from the message size (or a way to compute sets of
P-boxes from message size which have properties that preserve
the analysis-resistance of the system) would be original work
which I don't trust my math skills enough to do, so I would
have to go brute-force with it instead of being able to discern
a "minimal secure" solution that would be efficient.

I could in good conscience deploy something like this, if I
use an absurdly compute-intensive key schedule to prevent the
opponent from being able to use any fixed information about
the S-boxes.  I would initialize a CSPRNG with the key material,
then generate ~= 1800 bits from a CSPRNG to create a uniform
choice among all possible 8-bit permutations for every S-box.
It would defy analysis assuming no complete break of the CSPRNG,
but it would be absurdly compute-intensive, and not lightweight
at all. Someone with better math chops than me can probably
come up with a *much* more performant key schedule and/or
set of s-boxes than my ridiculous-overkill plan while not
sacrificing security.


				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150513/37ffe296/attachment.sig>