passphrases with more than 160 bits of entropy

[Travis H.]

Hi,

Does anyone have a good idea on how to OWF passphrases without
reducing them to lower entropy counts?  That is, I've seen systems
which hash the passphrase then use a PRF to expand the result --- I
don't want to do that.  I want to have more than 160 bits of entropy
involved.

I was thinking that one could hash the first block, copy the
intermediate state, finalize it, then continue the intermediate result
with the next block, and finalize that.  Is this safe?  Is there a
better alternative?
--
Security Guru for Hire http://www.lightconsulting.com/~travis/ -><-
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: pipad, was Re: bounded storage model - why is R organized as 2-d array?

[John Kelsey]

>From: [EMAIL PROTECTED]
>Sent: Mar 21, 2006 9:58 AM
>To: [EMAIL PROTECTED]
>Cc: [EMAIL PROTECTED], cryptography@metzdowd.com
>Subject: Re: pipad, was Re: bounded storage model - why is R organized as  
>2-d array?

...
>| Anyone see a reason why the digits of Pi wouldn't form an excellent
>| public large (infinite, actually) string of "random" bits?

>The issue would be:  Are there any dependencies amoung the bits of
>pi that would make it easier to predict where an XOR of n streams of
>bits taken from different positions actually come from - or, more
>weakly, to predict subsequent bits.

When you build this scheme, you have to compare it to all other ways
of generating random-looking keystream for a stream cipher.  That
means comparing it with generators which are guaranteed to be as hard
to predict output bits for as a large integer is hard to factor, for
example.  Beyond the coolness factor of pi, it's hard to work out what
additional guarantee we're getting from using it here.  

I don't know what the performance of the algorithm for generating the
next n bits of pi looks like, but I'm guessing that I can do a fair
number of AES/Serpent/Twofish/MARS/RC6/Blowfish/CAST/3DES/IDEA/RC5
calculations for the same cost.  And we know how to build a stream
cipher out of all those ciphers (running in OFB or counter mode) which
is guaranteed to be as strong as the strongest of them.  

It's all about tradeoffs between performance, security, and what
strong statements you can make about your security when you're done.
In some applications, I am willing to give up a lot of performance for
a solid proof of security; in others, I am willing to give up any hope
of a proof of security to get really good performance.

>   -- Jerry

--John Kelsey


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Linux RNG paper

[Heyman, Michael]

Gutterman, Pinkas, and Reinman have produced a nice as-built-specification and 
analysis of the Linux random number generator.

>From :

Following our analysis of the LRNG, we suggest the following recommendations 
for the design of pseudo-random number generators.

² Fixing the LRNG. The issues which were reported in this paper should be 
fixed. In particular, the LRNG code should be changed to prevent attacks on its 
forward security. The OpenWRT implementation should be changed to provide more 
entropy to the LRNG, or at least save its state during shutdown.

² Implementing a quota for the consumption of random bits. Random bits are a 
limited resource, and attackers can easily mount a denial-of-service attack 
(even remotely) by consuming random bits at a high rate. The common solution 
for this type of problem is to implement a quota system which limits the effect 
of each user, or each process, on the operation of other users of the same 
system. Such a quota system should be added to the Linux kernel.

² Adopting the Barak-Halevi construction. The Barak-Halevi (BH) construction 
and its analysis [3] are attractive in their simplicity, which clearly 
identifies the role of every component of the system, and enables a simple 
implementation. In comparison, the current LRNG construction is an overkill in 
some aspects (like the size of the pools or the number of SHA-1 invocations), 
but its complexity does not improve its security but rather hides its 
weaknesses. We suggest that future constructions of pseudo-random number 
generators follow the BH construction (and in general, try to "keep it simple").

² Since randomness is often consumed in a multi-user environment, it makes 
sense to generalize the BH model to such environments. Ideally, each user 
should have its own random-number generator, and these generators should be 
refreshed with different data which is all derived from the entropy sources 
available to the system (perhaps after going through an additional PRNG). This 
architecture should prevent denial-of-service attacks, and prevent one user 
from learning about the randomness used by other users

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: Creativity and security

[Olle Mulmo]

Unfortunately, they haven't. In Europe I get receipts with different  
crossing-out patterns almost every week.


And, with "they" I mean the builders of point-of-sale terminals: I  
don't think individual store owners are given a choice.


Though I believe I have noticed a good trend in that I get receipts  
where *all but four* digits are crossed out more and more often  
nowadays.


/Olle

On Mar 20, 2006, at 21:51, [EMAIL PROTECTED] wrote:


I was tearing up some old credit card receipts recently - after all
these years, enough vendors continue to print full CC numbers on
receipts that I'm hesitant to just toss them as is, though I doubt  
there
are many dumpster divers looking for this stuff any more - when I  
found
a great example of why you don't want people applying their  
"creativity"

to security problems, at least not without a great deal of review.

You see, most vendors these days replace all but the last 4 digits of
the CC number on a receipt with X's.  But it must be boring to do the
same as everyone else, so some bright person at one vendor(*) decided
they were going to do it differently:  They X'd out *just the last  
four

digits*.  After all, who could guess the number from the 10,000
possibilities?

Ahem.
-- Jerry

(*) It was Build-A-Bear.  The receipt was at least a year old, so for
all I know they've long since fixed this.

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to  
[EMAIL PROTECTED]



-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: pipad, was Re: bounded storage model - why is R organized as 2-d array?

[leichter_jerrold]

| Anyone see a reason why the digits of Pi wouldn't form an excellent
| public large (infinite, actually) string of "random" bits?
| 
| There's even an efficient digit-extraction (a/k/a "random access to
| fractional bits") formula, conveniently base 16:
| http://mathworld.wolfram.com/BBPFormula.html
| 
| I dub this "pi pad".
The issue would be:  Are there any dependencies amoung the bits of
pi that would make it easier to predict where an XOR of n streams of
bits taken from different positions actually come from - or, more
weakly, to predict subsequent bits.

I doubt anyone knows.  What would worry me is exactly the existence
of the algorithm that would make this approach workable:  A way to
compute the i'th digit of pi without computing all the earlier ones.

As a starter problem, how about a simpler version:  Take n=1!  That
is, the key is simply a starting position in pi - taken from a
suitably large set, say the first 2^256 bits of pi - and we use
as our one-time pad the bits of pi starting from there.  An
attackers problem now turns into:  Given a sequence of k successive
bits of pi taken from among the first 2^256 bits, can you do better
than chance in predicting the k+1'st bit?  The obvious approach of
searching through pi for matches doesn't look fruitful, but perhaps
we can do better.  Note that if pi *isn't* normal to base 2 - and
we still don't know if it is - this starter problem is soluable.

BTW, Bailey and Crandall's work - which led to this discussion -
ties the question of normality to questions about chaotic
sequences.  If the approach of using pi as a one-time pad
works, then all the systems based on chaotic generators
will suddenly deserve a closer look!  (Many fail for much
simpler reasons than relying on such a generator, but some
are untrustworthy not because we don't know of an attack
but because we have no clue how to tell if there is one.)


| Is this idea transcendental or irrational?
Mathematician's insult:  You're transcendental (dense and totally
irrational).
-- Jerry

-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

Re: Tunnels in Hash Functions: MD5 Collisions in 40 seconds

[alex]

Any time estimates for SHA-1 or SHA-2 attacks?

- Alex

> - Original Message -
> From: [EMAIL PROTECTED]
> To: cryptography@metzdowd.com
> Subject: Tunnels in Hash Functions: MD5 Collisions in 40 seconds
> Date: Sat, 18 Mar 2006 18:05:40 +0100 (CET)
> 
> 
> Congratulations to Marc Stevens, who described a method for fast
> collision attack on MD5!
> 
> Just now (! it is a collision !) I have finished the translation of
> my paper Vlastimil Klima: "Tunnels in Hash Functions: MD5 Collisions
> Within a Minute".
> 
> It is based on a new method, tunneling. Using it on MD5 it gives a
> collision in 40 seconds on a 3 GHz Pentium 4.  (Actually I used two
> times slower notebook with the time about 80 seconds.) I expect the
> publication on eprint also, but I will put in on my web together
> with the source code of the program in one or two hours. It is
> http://cryptography.hyperlink.cz/MD5_collisions.html
> 
> Vlastimil Klima
> http://cryptography.hyperlink.cz/
> 
> --
> Od: "Weger, B.M.M. de" <[EMAIL PROTECTED]>
> Komu: cryptography@metzdowd.com
> Predmet: MD5 collisions in one minute
> Datum: 17.3.2006 - 19:37:20
> 
> > Hi all,
> >
> > You might be interested in knowing that my MSc student
> > Marc Stevens has found a considerable speedup of MD5 collision 
> > generation. His improvements of Wang's method
> > enables one to make MD5 collisions typically in one
> > minute on a PC; sometimes it takes a few minutes, and sometimes 
> > only a few seconds.
> > His paper (shortly to appear on the Cryptology ePrint
> > Archive) can be found on http://www.win.tue.nl/hashclash/,
> > where we've also made his software available (source code
> > and a Win32 executable).
> > Grtz,
> > Benne de Weger
> 
> 
> 
> -
> The Cryptography Mailing List
> Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]

>


-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]