[Cryptography] I broke a cipher this week.

[Ray Dillinger]

Don't get excited:  It was not a major cipher and nothing
depends on it.  And I'm allowed to talk about it as long as I
don't mention the company or the project they had intended to
use it for.

And TL:DR; if you don't want to read details, just consider the
fact that a linear congruential transformation makes a hell of
a good way to distribute 64 bits of output from one layer of
S-boxes to the inputs of your next even if your S-boxes are a
lot smaller than 64 bits.  It's not crypto-secure as an S-box
transformation, but it provides a really good amount of
diffusion, and is computationally cheap on 64-bit machines
relative to the usual bit-slicing, and is massively parallel
on GPUs.

Now, for the people who are willing to listen to me ramble
instead of just reading the TL:DR, a little story.

I had mentioned to a friend that I was frustrated by a lack of
ciphers not yet broken that were within my own ability to break,
and he (and his boss) obliged me by submitting for my scrutiny
a proprietary cipher that an engineer at their workplace had
come up with, which thank goodness, had not yet been included
in a product.  My friend had been trying to convince his boss
that proprietary crypto algorithms were not a good idea, and
I'm pleased that I managed to give the strongest possible
evidence that the one they were about to use is in fact not a
good idea.

That said, its basic round function (what they wanted to use for
an S-box) would make a hell of a good P-box to distribute 64
bits of entropy among next round's S-boxes.  So I thought I'd
share it.

The cipher designer (professional programmer, not professional
cryptographer) was using a perturbed modular multiplication
transformation as an S-box.  It consisted of taking a 64-bit
input (C1) and two bytes from the key schedule.  The two
bytes (which I'll call A and B) were used to perturb the
output of the LCT like so.

C2 = ((C1 x A) + B modulo 2^64)

To generate C2 (output).  In fact a Linear Congruential
Transformation with key-schedule variables instead of
constants.  Then his P-boxes were slicing that up into
8 bytes and sending one to each of the 8 S-boxes of the
next round. (working on 64-byte blocks). Decryption was
with plain subtraction and a table of modular inverses.

The particulars of his cipher aside, a linear congruential
transformation is absolutely not a bad 64-bit P-box for a
real cipher, which is what I thought I'd point out here.
You can do your operations on any size S-box you want (that
divides 64) and use an LCT to split the bits up among the
next set of S-boxes.

But as for his cipher? Table of modular factors of each of
the 256 bytes the input might have been multiplied by, modular
division of set of numbers resulting from permutations of
the other 7 bytes plus 256 possible values for the unknown
input, statistical correlation of small factors under 16,
rinse, repeat, recursive search seeking the path with the
greatest bias in factors <23 available at each round (he
was using 4 rounds), program that can break the cipher in
the time it takes to get your finger off the return key.
And extends to *ANY* number of rounds with a constant
average work factor required per round.

I know that this is no tremendous feat in terms of crypto,
but I'm still pleased with myself; this is the first time
I've actually broken a cipher *PREVENTING* it from being
used in an insecure product, and it was a complete break
allowing the awesome demo of actual plaintext recovery
from a single block of encrypted output, which is highly
understandable even to those who do not speak math as a
native language.

Though I felt bad for the engineer; he actually made a
pretty good try for a beginner. If his 2-byte "perturbation"
at each round had selected from a better set of
transformations (had been a choice of 1024 different
64-bit XOR masks which exclude all rotations of each other
and the 64 possible bit-rotations for example rather than
an 8-bit multiplicand and 8-bit addend), or if his P-
boxes had sliced the output into bits instead of bytes
and directed them so that each byte of S-box input was
constructed from a different *combination* of bits from
the bytes of the previous S-box output? I could have
undone the trivial last round of P-boxes, but I don't
have math skillz to get further than that.

Anyway, someone else has better math skillz than me, so
instead of saying "this would be secure if..." and
almost certainly being wrong, I pointed them at two well-
tested and widely-scrutinized libraries.

				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/20150522/83d28804/attachment.sig>