[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20110514212243.GA23860@openwall.com>
Date: Sun, 15 May 2011 01:22:43 +0400
From: Solar Designer <solar@...nwall.com>
To: crypt-dev@...ts.openwall.com
Subject: Re: alternative approach
David, Yuri -
On Sat, May 14, 2011 at 03:47:06AM +0400, Solar Designer wrote:
> I've experimented with this today. Attached is a program that
> demonstrates a heavily cut-down Eksblowfish-like algorithm.
I've attached a new revision of it. This one compensates for my removal
of Blowfish's P array better. Although the previous revision did not
have full internal state collisions for the inputs I was throwing at it,
it would produce a bit fewer than expected 16-bit "encrypted" outputs -
e.g., for 65536 different inputs, it would typically produce between
41100 and 41400 different outputs, whereas ideally it'd produce around
41427 of them. The new revision correctly produces slightly fewer or
slightly more than 41427 different outputs on this test (with different
sets of inputs).
This expected number may be calculated as (1-1/e)*65536, which assumes
uniform distribution of outputs when encrypting a constant with
different keys, and that 65536 is large enough for this approximation to
be valid (it is).
I also used the following little program (which I wrote many years ago)
to calculate the expected number of different outputs of a certain size
(in bits) for an arbitrary number of different inputs:
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
long double v, x, y;
int n;
int main(int argc, char **argv) {
v = pow(2.0, atof(argv[1]));
x = 0; n = atoi(argv[2]);
y = v * (1.0 - pow((v - 1.0) / v, n));
while (n--) x = x * ((v - 1.0) / v) + 1.0;
printf("%Lf\n%Lf\n", x, y);
return 0;
}
It calculates the same thing twice, in different ways, out of paranoia.
For 16-bit outputs, this gives 65504 for 500000, or 65535.98 for 1000000
inputs. The new revision of bflike.c passes these tests, too - e.g.,
here are two invocations of it on two different sets of 500000 inputs:
$ ./bflike < w500k1 | sort -u | wc -l
ntot/neq = 256.01
65505
$ ./bflike < w500k2 | sort -u | wc -l
ntot/neq = 256.00
65512
The ntot/neq is another sanity check. (Should be close to 256.00.)
Also, there's a check for looping internal state - if this were
detected, a message would be printed to stderr. (It would be a problem
because it'd allow an attacker to bypass further computation after
similarly detecting a loop.)
I am using those 16-bit outputs for testing only. If we end up actually
using this algorithm, we'd be passing its entire internal state into
something like SHA-256. (Unless it is somehow difficult or costly to
route those internal state bits to a SHA-256 core or to have them sent
to the host system.) So the previous revision would have been fine as
well. But I prefer to have some safety margin.
I also introduced optional bit order reversals, which don't affect the
algorithm's properties significantly. These need more thought - we'd
want to use them in such places that a sequential software
implementation wouldn't move them out of the loop (such as by
re-ordering array elements if we reverse the bits in its index).
Yuri - my request to you remains the same. You don't need to update to
this new revision, you may use the old one. I merely want to get an
idea of the logic cell count, as well as of why a certain number of
logic cells is needed to implement something like this (some sort of
diagram would help). I think you could want to implement the two rounds
at once (including their four S-box lookups), or maybe even four at once
(assuming Nrounds set to 4 or larger in the program). I think it is
possible to compute many rounds at once (per one clock cycle) as long as
the S-boxes don't change during them (they only change after Nrounds is
reached). Of course, this should result in a higher signal propagation
delay and thus lower maximum clock rate, but that's fine. Whatever turns
out to make efficient use of resources. Then we'd need to compare this
against a round of DES.
Thanks,
Alexander
View attachment "bflike.c" of type "text/plain" (4975 bytes)
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
