Cryptography-Digest Digest #354, Volume #12 Thu, 3 Aug 00 22:13:00 EDT
Contents:
Re: Cracking RC4-40 in FPGA hardware ("CMan")
Observation on MDS matrices (tomstd)
Re: OTP using BBS generator? (Tim Tyler)
Re: Let us have Lattice (Tim Tyler)
Re: PRNG cryptoanalysis (Tim Tyler)
Re: OTP using BBS generator? (Mack)
Re: Elliptic Curves encryption ("Trevor L. Jackson, III")
Re: Cracking RC4-40 in FPGA hardware (David A. Wagner)
Re: Small block ciphers (Benjamin Goldberg)
Re: Small block ciphers (Benjamin Goldberg)
Re: IV for arfour (Benjamin Goldberg)
Re: A non-linear extension of the Hill cipher (Benjamin Goldberg)
Re: Proving continued possession of a file ([EMAIL PROTECTED])
Re: Cracking RC4-40 in FPGA hardware (Paul Rubin)
Re: New William Friedman Crypto Patent (filed in 1933) - OFF TOPIC ("John A. Malley")
----------------------------------------------------------------------------
From: "CMan" <[EMAIL PROTECTED]>
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: Thu, 3 Aug 2000 16:00:21 -0700
Sorry for the garbled (truncated) message. I think I funally have my act
together...
OOPS!!!!
I forgot to mention...while the Word Document key is truly 40 bits (actually
48 bits because there is some re-keying in an easy to guess way), but the
problem is the RC4 key is actually 128 bits. You see, Word first takes the
40 bit (48) bit document key and computes a hash of this document key and
uses that to schedule RC4.
There are only 40 bit of entropy, of course, in this RC4 key, nevertheless,
you either must compute the hash after each key guess or you must try all
2^128 keys :--)). Since the later is not within reason, you must compute
the hash once for each key.
I believe SSL also uses an MD4/5 hash also so this same difficulty arises
there.
I don't think MD4/5 is easy to implement in hardware. (I could be wrong on
this point!!)
I don't think I have ever seen an application that did not hash the key
before running the RC4 key schedule. Just laying out the 40 bit key and
repeating it in the RC4 S-box and then running the key schedule
significantly reduces the computational load associated with a brute force
attack.
Unless the RC4 hardware and the MD4/5 hash computation run at approximately
the same speed, the process sort of falls apart. The hardware will just sit
there waiting for new hashes to load.
JK
--
CRAK Software
http://www.crak.com
Password Recovery Software
QuickBooks, Quicken, Access...More
Spam bait (credit E. Needham):
root@localhost
postmaster@localhost
admin@localhost
abuse@localhost
webmaster@localhost
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
<[EMAIL PROTECTED]> wrote in message news:8mco74$erk$[EMAIL PROTECTED]...
> In article <8mcbbp$[EMAIL PROTECTED]>,
> "Paul Morris" <[EMAIL PROTECTED]> wrote:
> >
> > Fundamentally, Paul suggested that multiple (cheap) FPGAs, running
> multiple
> > threads each, could potentially brute-force break an RC4-40 in, say,
> 200
> > hours or less. Paul coined the name 'Shallow Crack' in reference to
> the EFF
> > Deep Crack machine. Does anybody have any comments on the feasibility
> of
> > this?
>
> Unless I've slipped a decimal point, this should be very easy.
> The limiting factor in RC4 looks like the table initialization.
> For each of 256 iterations, it reads one value from the table,
> does some computation, then swaps two values. If we assume a 2 ported
> ram, and logic is free compared to memory (true for FPGAs) then this
> should take 3 cycles.
> 1) read the table entry, figure out which two to swap
> 2) read the two values.
> 3) write the two values.
> so we have 3x256 or 768 cycles for each trial key.
>
> Then we need to decypher some text, and either see if it's OK
> (known plaintext) or at least plausible (unknown plaintext).
> Each byte takes a few cycles, probably 40 bytes are plenty,
> so another 120 cyles.
>
> We need to report results, cycle to the next key, etc., but 1000 cycles
> should be plenty to check one key.
>
> Each cycle requires a memory read and a pair of 8 bit adds, so 10ns
> looks like a good estimate. Then we have 10 usec/key, or 10^5 keys
> per second. 2^40 is about 10^12, so even with one such piece of
> hardware we have 10^7 seconds, or about 2800 hours to search all
> keys. We expect success on the average in 1/2 this time, or 1400
> hours.
>
> But even the smallest and cheapest Xilinx FPGA (Spartan) has 4 of
> these blocks, so we have 350 hours average. The bigger ones have
> 32 independent memory blocks, for an average time of 43 hours
> per chip.
>
> We can run as many chips as we want in parallel, of course, so if
> we had 43 big chips we get an average solution time of 1 hour, and
> a max of 2 hours. Of course it might be more cost effective to use
> more of the cheaper chips - that's an engineering tradeoff.
>
> So this seems pretty easy. I'd approach it like this:
> 0) Write a copy of your algorithm in Verilog or VHDL and
> simulate it (with say 10 bit keys). See how many cycles it
> takes per key.
> 1) Get a development board for a PC with a Xilinx on it (Any
> Xilinx - whatever is most convenient)
> 2) Get a single copy of the algorithm working and solving a
> bigger but still tractable problem (say 28 bits)
> 3) Cram as many copies as you can into a single FPGA and demo
> that with 36 bit keys.
> 4) Build or buy a board with lots of FPGAs and program/use
> that with full 40 bit keys.
>
> Everything after step 2 is just engineering and not cryptography,
> but makes a much more impressive demo.
>
> Lou Scheffer
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
Subject: Observation on MDS matrices
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 03 Aug 2000 16:31:46 -0700
Just wanted to know if this is right...
With a 4x4 mds matrix applied to an input the different in the
input/output tuples is at least five right?
Well if we consider two inputs (a, b) where b differs by four
from 'a' then the outptu (f(a), f(b)) must only differ by one
place at the most. This means that when applied iteratively we
get
f(f(f(a))) ... where all the odd rounds have the max difference
and all even rounds have the minimum.
Has anyone tried to apply this to twofish?
Food for thought...
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 3 Aug 2000 23:18:14 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
: I claim it is deceptive to call the reduced scheme BB&S. It is also
: deceptive to claim that any system which we can make more secure by
: our own action is absolutely secure. [...]
AFAICS, nobody's claiming this for it in the first place.
They're claiming that it's provably as hard as a known math problem.
In this instance I believe factoring the modulus is usually a more
powerful attack than a brute force search through the possible seeds,
(assuming these are of equivalent size).
There are other ways to improve the security of this system, besides
weeding out short cycles. XOR with another strong PRNG using the same
seed is quite likely to work. Then - /even/ if the modulus is factored
- the generator may still be able to resist attack.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Breast is best.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Let us have Lattice
Reply-To: [EMAIL PROTECTED]
Date: Thu, 3 Aug 2000 23:24:09 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Finally, it is a linear transformation. [...]
Yes. This appears to make it next-to-useless as an encryption device.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Breast is best.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: PRNG cryptoanalysis
Reply-To: [EMAIL PROTECTED]
Date: Thu, 3 Aug 2000 23:28:27 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
: Mack wrote:
[analysis of LFSR/LCGs?]
:> The Blum-Blum-Shub paper showed that the LCG generator was
:> weak.
:>
:> The LFSR in its simplest form outputs its state as its output. [...]
:>
:> Both of these generators fail various statistical tests.
: This observation is not meaningful. For any LFSR there is a test that
: can distinguish it from random. [...]
The latter sentence appears to me to capture most of the intended meaning.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Breast is best.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 04 Aug 2000 00:43:36 GMT
Subject: Re: OTP using BBS generator?
>I know I'm arriving rather late to the party but, while Mr Ritter and I have
>been on differing sides of discussions before, I agree with him completely
>in this case. What he has suggested is to verify the lack of a short cycle,
>through a relatively cheap mechanism (certainly cheaper than the compromised
>security that could result is that check would have been failed). I find
>this to be solid reasoning, and something that should be done by anyone
>making use of BBS in this fashion.
>
>On a more personal note, I've noticed that this conversation has drifted
>towards being personal insults, please try to remember that Mr Ritter has
>been a long standing member of this group, and has build a quite solid,
>respected position, all you are doing is harming your credibiltity, as can
>be rather easily seen by looking at Mr Ritter's response, which was to the
>best of my knowledge completely factual, and dealt more with the issue at
>hand than his attacker.
> Joe
>
>
I agree with Terry Ritter also. There are several types of cycles
possible with the BBS generator. It is important that the
primes used be "special". In that case the cycle will be two or
we have found a multiple of a factor of N for a short cycle. It is
easy to check for both of these conditions.
Using a single bit from each X increases the chance of the cycle
of the output being two by a great deal, does anyone have an
analysis of how often this occurs?
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
Date: Thu, 03 Aug 2000 20:55:33 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Roger Schlafly wrote:
> "Trevor L. Jackson, III" wrote:
> > I don't consider it to be _experimental_ evidence. Do you?
>
> Yes. If a bunch of ciphertexts pass a bunch of randomness tests,
> then that is experimental evidence. Not sure what your objection
> is -- would you prefer the term "empirical evidence"?
Hmm. I don't want to answer that hastily. It's a good question.
There are several issues, but I can't express them succinctly, which means
they need need work. Or revision.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: 3 Aug 2000 18:11:47 -0700
A couple of years ago Ian Goldberg and I tried this.
We got pretty disappointing results; our FPGA implementation of RC4
was significantly slower than a general-purpose CPU, due to the costs
of all those accesses to RAM. In retrospect, it's perhaps not too
surprising -- RC4 uses many of the operations that general-purpose
CPU's have been seriously optimized for.
On the other hand, I've heard that other folks have gotten very good
results using a different line of FPGA's, so perhaps our results were
pessimistic.
Anyway, if you want to read about our efforts, see our paper at
http://www.cs.berkeley.edu/~iang/isaac/hardware/main.html
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Small block ciphers
Date: Fri, 04 Aug 2000 01:34:11 GMT
Mack wrote:
[snip]
> I am more interested in the theoretical properties of a small block
> cipher. For example, If we change the key after every second
> encryption. Can an attacker find the key? Or if we change the key in
> some linear manner after every encryption can an attacker find the key
> for N encryptions where the key size is N*M?
If you change the key after [every other] encryption, it becomes
something like a stream cipher, not a block cipher.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Small block ciphers
Date: Fri, 04 Aug 2000 01:34:21 GMT
Mok-Kong Shen wrote:
>
> Mack wrote:
>
> > I am more interested in the theoretical properties of a small block
> > cipher. For example, If we change the key after every second
> > encryption. Can an attacker find the key? Or if we change the key in
> > some linear manner after every encryption can an attacker find the
> > key for N encryptions where the key size is N*M?
>
> I believe that, if the block cipher (and hence the key size) is small,
> the opponent will simply do brute-force, for that's easy for him,
> while a well-designed large block cipher is impractical to brute-force
> and he has therefore to resort to more intelligent means, if
> available.
Having the block size of a cipher small does *not* imply that the key
size is small. An 8-bit block cipher can have as many as 256! possible
keys. Breaking such a cipher is usually done with either some
statistical analasys, or a codebook attack, or with known plaintext.
Figuring out what the key is may not actually be necessary, especially
if it uses, for example, an 16 byte key to simulate a 256 byte table.
If the key is changed in a linear manner, you get something like a
dynamic substitution cipher [I think]. If the key is changed in a
non-linear manner, you get something like RC4/ARC4. Regardless of how
your key-changing takes place, you're adding a significant amount of
state, which moves your cipher out of the realm of block ciphers, and
into the realm of a stream ciphers.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: IV for arfour
Date: Fri, 04 Aug 2000 01:34:30 GMT
Andreas Sewe wrote:
>
> Well, any stream-cipher needs an IV, and in most cases it is
> altogether sufficant to XOR the key K with the IV to get the
> session-key K_s.
Why XOR? Why not concatenate? With a 256 bit key, and 64 bit IV, you
*can* use all of your key+IV to initialize the state of the RC4
generator.
>
> But now, arcfour doesn't use a simple n-bit value as key K, but a
> permutation of 256 elements. Of course, this permutation, the internal
> key K_i, is generated - in Rivest's implementation - out of a 2048
> bit, i.e. 256 bytes; the external key K_e. So you can simply xor an
> 2048 bit IV with the external key, perform Rivest's algorithm of
> generating the internal key, and you get an internal key modified by
> the IV.
>
> But, the ugly is, this method relies heavily on the algorthim for
> generating internal keys.
Hmm, considering that RC4's method of generating the internal state from
the key is designed to avoid short cycles, mixing your IV with the key
before generating the state seems [to me] to be a good idea.
> Now suppose I get my permutations toying with 256 coloured marbles,
> getting real random ones.
You mean numbered, not colored marbles, cause most people can't
destinguish between 256 different colors :)
Umm... You've got an array with 256! possible states. Are you using
this as your RC4 internal state, bypassing normal key setup, or are you
using this as your IV, with the idea of combining it with RC4's state?
> But now, I can't use the XOR method described above to get
> my session key out of two permutations, generated by the "marble
> method". So I have to link two permutations, key K and IV, to get a
> third permutation - the session key K_s.
>
> /* in C it can be done by the following code */
>
> typedef char permutation[256];
> permutation k, k_s, iv;
> int n;
>
> for(n = 0; n < 256; n++)
> k_s[n] = k[iv[n]];
>
> Are there any fundamental weaknesses, perhaps a chosen-key-attack?
Your thinking of taking the state produced by RC4's key schedule, which
was carefully designed to avoid short cycles, and modifying it using an
IV that's essentially random, to produce a new internal state which
might very well have a short cycle in it. This is Bad.
>
> Andreas Sewe
>
> PS: Well, for those paranoid one, who fear one session key might be
> found by an attacker, the above method is not one-way. Knowing
> K_s and IV, your attacker gets key K (and all your other
> session key, using this one).
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: A non-linear extension of the Hill cipher
Date: Fri, 04 Aug 2000 01:34:43 GMT
Some of what you are describing sounds very like Mark Wooding's "Storin"
cipher. Enciphering is as follows:
X[i], Y[i], Z[i] = intermediate values.
K[i] : Round keys.
Ma : a 4x4 matrix, invertable under integers mod 2**24
Mb : the inverse of Ma; used for decryption
Z[-1] = Plaintext, split into a vector of 4 24-bit values.
For i = 0 to 7
X[i] = Z[i-1] XOR K[i]
Y[i] = (X[i] * Ma) MOD (2**24)
For j = 0 to 3
Z[i][j] = Y[i][j] XOR (Y[i][j] >> 12)
end For j
End for i
Ciphertext = Z[7] XOR K[8]
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Proving continued possession of a file
Date: Fri, 04 Aug 2000 01:52:20 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mark Wooding) wrote:
> But then there's an additional tweak for constructing the
> noninteractive proof: you must use some unpredictable source
> for the timing information. The date can be predicted easily,
> so dates aren't a good source of hash preimage material.
> Using, say, lottery numbers, racing results and/or newspaper
> headlines works much better here.
True. I suggested the NYSE stock prices in the algorithm I posted.
I preferred them to racing results or newspaper headlines because
they're available online from many sources, are archived for long
periods, and could be dangerous to falsify.
> [1] While I don't have any problem with people wanting to retain
> anonymity, I do wish they'd give some more usable pseudonyms. ;-)
> -- [mdw]
Perhaps it would be more usable to refer to the "LCB" with which all
the posts are signed, rather than using the random email address. :-)
LCB
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: 4 Aug 2000 02:08:19 GMT
In article <8md58j$4r5$[EMAIL PROTECTED]>,
David A. Wagner <[EMAIL PROTECTED]> wrote:
>A couple of years ago Ian Goldberg and I tried this.
>
>We got pretty disappointing results; our FPGA implementation of RC4
>was significantly slower than a general-purpose CPU, due to the costs
>of all those accesses to RAM. In retrospect, it's perhaps not too
>surprising -- RC4 uses many of the operations that general-purpose
>CPU's have been seriously optimized for.
Current FPGA's have a lot more logic available than the Altera parts
you used, plus they have blocks of dedicated RAM so you don't have to
burn logic blocks for the sake of memory. They just don't have the
restrictions they did a few years ago. For example, a $10 Xilinx part
can simulate a complete 8035-style microprocessor at something like
10x the speed of a real 8035.
More info: http://www.xilinx.com/products/spartan2/index.htm
>From looking at the specs (and I'm *not* a hardware whiz) it looks to
me like the FPGA can run RC4 at least as fast as a high-end
general-purpose CPU (even if not faster), but at much lower cost.
It's a lot more reasonable to make a board with 50 FPGA's at $10 each,
than a board with 50 Pentiums and their surrounding support glue.
If you get a chance to look at the Xilinx page I'd be interested to
know your assessment.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: New William Friedman Crypto Patent (filed in 1933) - OFF TOPIC
Date: Thu, 03 Aug 2000 19:07:49 -0700
David Blackman wrote:
>
>
> Previous machines had actually had more success than the Wrights did in
> 1903, though not as much success as the Wrights had in the next few
> years. I think the Wrights have gone down in history because they were
> involved continuously in aircraft development from about 1897 through to
> 1910 when aircraft actually became practical. Most of the other early
> pioneers either started later or gave up earlier or got killed.
>
> The Wright brother's aircraft were examples of good engineering
> (especially in the safety department) but had nothing particularly new
> in them. I don't think they particularly deserved a patent for anything.
I disagree. If memory of the history of aircraft stability and control
technology serves,
their most significant innovation was wing warping - which evolved into
the aileron.
They came up with the concept of differential lift across the wings to
rotate the aircraft and allow it to turn to the left or the right (i.e
one wing drops, the other rises and a component of the total lift
vector perpendicular to the wing thus "pushes" the aircraft off its
current heading.)
An Amazing Idea. Before this no one knew how to change the
heading/direction of a powered aircraft.
> They did deserve fame and commercial success.
Yes, especially for the aileron.
John A. Malley
[EMAIL PROTECTED]
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
