Cryptography-Digest Digest #36, Volume #12 Thu, 15 Jun 00 13:13:01 EDT
Contents:
Re: salt length? (tomstd)
Re: primality tests (Bob Silverman)
Re: Cipher design a fading field? ("Douglas A. Gwyn")
Re: Cipher design a fading field? ("Douglas A. Gwyn")
Re: Cipher design a fading field? (Mark Wooding)
Re: Comments/analysis requested: stream cipher derived from hash function (SHA-1)
(Lon Willett)
Re: Random sboxes... real info (Tim Tyler)
Re: Application specific SBoxes in Blowfish? (Tim Tyler)
Re: small subgroups in Blum Blum Shub (Tim Tyler)
Re: salt length? (zapzing)
Re: Evidence Eliminator Dis-Information Center ("donoli")
Re: Why the golden ratio? (Tim Tyler)
Re: Comments/analysis requested: stream cipher derived from hash function (SHA-1)
(Lon Willett)
Re: quantum cryptography at nytimes.com (Roger Schlafly)
Re: Onefish (Twofishes sibbling) (Tim Tyler)
Re: quantum cryptography at nytimes.com (Roger Schlafly)
----------------------------------------------------------------------------
Subject: Re: salt length?
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 15 Jun 2000 08:27:43 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>> In article <8iak3p$4ejql$[EMAIL PROTECTED]>, "Elros"
>> <[EMAIL PROTECTED]> wrote:
>>
>> >For use with a stream cipher (e.g. RC4), what's a good
length for a
>> >salt (S) that gets concatenated (&) to the user supplied key
(U)
>> >before S & U gets fed into the cipher?
>>
>> That's a stupid idea.
>
>No, it's not. For someone who's still a self-confessed
beginner, you're
>very quick to label others' ideas as stupid. And while the
excessive
>`humility' of some other regular posters has begun to grate, a
certain
>degree of politeness and caution wouldn't go amiss.
>
>And if you are going to abuse other posters, at least take a
leaf from
>Bob Silverman's book and be both (usually) correct and witty
with it.
>
>> You should feed the RC4 key schedule the hash of the password
and
>> salt.
>
>Why? RC4's key schedule can cope with a reasonably-sized
password and a
>salt just fine. While it's true that RC4 does leak a little
bit of key
>information, this is easily fixed by spinning the RC4 generator
around
>for a bit, e.g., by generating and discarding 1024 bytes of
output, and
>this is recommended practice for using RC4 anyway.
>
>If memory serves, it's the later bytes of key which are more
likely to
>be leaked in the early output bytes. By submitting the user
password
>and the salt, in that order, to the key schedule, we make it
likely that
>the information leaked is the salt, which is sent in the clear
anyway.
>
>If you just use the hash, and you do leak key bytes then you
reduce the
>(fixed) search space of the hash output. For example, if you
use a
>20-byte (160-bit) hash, like RIPEMD-160, and leak 8 bytes,
you're left
>with a space of `only' 2^{96} bits to search.
>
>The `right' solution would seem to be to use a pseudo-random
function,
>keyed from the supplied password and salt, to fill RC4's 256-
byte key
>space. But we have a pseudo-random function: RC4! (Well, it's
at least
>as good as RC4 is, anyway.) So why don't we just use that? ;-)
True, but I thought part of the attack revolved around certain
classes of keys used in RC4? Either case I still think using a
hash is a good idea. It's a better "feed" for the RC4 schedule
and you can still dump bytes afterwards...
>> The salt should be long enough so that's it's never used
twice (with
>> high probability). If you are sending a message a day then
just use
>> the time_of_day in seconds.
>
>No. It also needs to be long enough to dissuade precomputed
dictionary
>attacks. There are 86400 seconds in a 24-hour period; while
this is
>larger than the Unix password salt space, I'm not sure it's
large enough
>for now. I'd recommend choosing a 64-bit random string.
I meant "time_since_1970" sorry...You could just as easily use a
64-bit string though...
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: primality tests
Date: Thu, 15 Jun 2000 15:25:43 GMT
In article <8ianjq$r15$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> hello all,
>
> when i implement probabilistic primality tests,
> i know that
>
> with Millrob for one base error possibility 0.25
False. The probability is bounded above by 1/4, but the actual
probability depends on the size of p.
> (and with n bases (0.25)^n )
False. See below.
> with Lehman 0.5
False.
> with Lucas 5/16
False.
> with Frobenius 1/7710
False.
>
> say that i implement 20 bases with MillRob i get (0.25)^20
See the HAC, tables 4.3 and 4.4 and the related discussion.
See:
Damgaard, Landrock, & Pomerance
Average Case Estimates for the Strong Probable Prime Test
Mathematics of Computation Vol 61 (1993)
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Thu, 15 Jun 2000 15:12:22 GMT
Tim Tyler wrote:
> However the original question was "if program size is bounded, does the
> halting problem exist for that set of programs?"
The original question was whether cryptanalysis was equivalent to
solving
the halting problem.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Thu, 15 Jun 2000 15:17:29 GMT
Tim Tyler wrote:
> This is irrelevant - a program exists which specifies which program
> halts, and which does not.
No, there is no such program.
If there were, we could apply it to the rather small program that
tests successive combinations of integers (in increasing order) and
halts when it finds one for which Goldbach's conjecture is false.
That would settle Goldbach's conjecture one way or the other.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Cipher design a fading field?
Date: 15 Jun 2000 15:51:08 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Tim Tyler wrote:
> > This is irrelevant - a program exists which specifies which program
> > halts, and which does not.
>
> No, there is no such program.
I think I'm with Tim on this one.
> If there were, we could apply it to the rather small program that
> tests successive combinations of integers (in increasing order) and
> halts when it finds one for which Goldbach's conjecture is false.
> That would settle Goldbach's conjecture one way or the other.
My understanding is that the truth of Goldbach's conjecture is currently
unknown, although not shown to be unknowable. If so, then the above is
quite correct. Unfortunately, Tim's argument is nonconstructive. Given
Tim's program, we could indeed settle Goldbach's conjecture, but we
don't have it and Tim's argument doesn't supply us with it, so it doesn't
help. Indeed, settling Goldbach's conjecture would be a prerequisite
(just one of many) for supplying Tim's program with its lookup table. I
don't see that this fundamentally affects the validity of the argument,
though.
-- [mdw]
------------------------------
From: Lon Willett <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Comments/analysis requested: stream cipher derived from hash function
(SHA-1)
Date: Thu, 15 Jun 2000 15:52:39 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
[snip]
> I don't believe it's considered so important in a PRNG for use as a
stream
> cypher as for some other uses - e.g. key generation.
Correct. I'm not really interested in running this a stream cipher.
It's just that when there is no entropy added, then a PRNG is really
just a stream cipher, so the same analysis applies. i.e. any weakness
as a stream cipher is a weakness in the PRNG, albeit less critical.
[snip]
> Iterating such a
> procedure may cause gradual "entropy drainage" from the internal state
-
> and significantly reduce the eventual expected cycle size.
Good point. But probably not really an issue, given a good hash
function. I am interested in a PRNG that will run on a machine in a
_very_ controlled environment, with little environmental entropy
available. And for customers that don't necessarily trust the HW RNGs.
But since this construction starts with twice as many bits of entropy as
its expected strength is, it will probably take a long time before half
the entropy is lost (at which point it becomes important). Hopefully
longer than even my application requires.
> An alternative strategy that makes runnung the generator backwards
> difficult, but retains a bijective property that ensures no entropy
from
> the seed is destroyed involves the use of a public key encryption
> algorithm. A public key is generated, and the private key is
> *destroyed*. The internal state of the generator is regularly
encrypted
> with the public key. Since the private key is not available, the
> generator can't be run backwards - without determining what the
private
> key is.
[snip]
Interesting idea. Another thought is just to base it on the DLP,
without worrying about using asymmetric crypto per se. e.g. let P be a
large prime, and G a primitive element mod P. Then, take the sequence:
X[i+1] = G ^ X[i] mod P.
This generates a nice sequence of values in the range 1 .. P-1, and is
not (easily) reversible. Surely someone has analyzed this. What are
its properties?
> __________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
> |im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA
GUPPY.
Thanks for the ideas.
/Lon
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Random sboxes... real info
Reply-To: [EMAIL PROTECTED]
Date: Thu, 15 Jun 2000 15:52:05 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> David Hopwood <[EMAIL PROTECTED]> wrote:
:> : tomstd wrote:
:> :> Well those 2^128 permutations out of the entire (2^64)!
:> :> permutations are strong with respect to diff and linear
:> :> analysis.
:>
:> : I think you may be labouring under a misapprehension - the 2^128
:> : permutations selected by the key are not stronger than a permutation
:> : selected at random from the entire space of (2^64)! possibilities.
:> : In fact, a method for selecting a permutation uniformly at random
: ^^^^^^^^^^^^^^^^^^^
:> : from that space would be as secure as a keyed permutation (a.k.a.
:> : block cipher) of that size can possibly be.
:>
:> That last seems questionable.
: Not at all.
Well, I'm questioning it, anyway ;-)
:> The space of all possible permutations contains the identity
:> transformation - which is not strong.
: It is not specific permutations that are strong or weak; it is the
: method of selecting them.
Specific permutations /can/ be weak. You you design a cypher by picking
2^128 128 bit permutations at random (in a stupendous LUT) and
all the permutations happen to be liner the result is a weak
cypher.
The method of selection may not be visible to an attacker. He may see
a whole bunch of messages under the same key - and be asked to perform
analysis. Weakness /cannot/ depend only on how permutations are selected.
It must lie - at least partly in the actual transformations employed.
: The identity transformation occurs with probability 1/((2^64)!), which
: is exactly the probability that it *should* occur with for a maximally
: secure block cipher.
It is that that I'm questioning. A random permutation is extremely secure
- but a random secure permutation would (in principle) be better - AFAICS.
: Worrying about a permutation selected uniformly at random (if it were
: possible to do that) being weak, is just as bogus as worrying about
: a perfectly implemented OTP having an all-zero keystream.
This seems completely false. If an OTP has an all-zero keystream, the
attacker can't possibly tell. If a block cypher used with a particular
key happens to be the identity transformation, it may well be pretty
obvious from the cyphertext. There will be no diffusion of the plaintext
in the cyphertext. This will show up even if chaining modes are used
to obscure the results.
: Not only is it not a practical weakness, it is not a theoretical weakness
: either: the identity transformation occurs with the probability we
: would expect for a keyed permutation that hides all information about
: its input.
It /could/ be a weakness. Consider the instance where a 128-bit keyed
block cypher is built using random selections - and all the selections
all happen to be linear. The resulting cypher system is garbage. Every
key is of no practical use. This happens despite the construction
technique being a "theoretically ideal" one.
Don't get me wrong. I know what the chances of hitting on these
permutations at random is. I'm not suggesting for a moment that anyone
should care about the possibility of hitting weak permutations when
selecting them at random.
I doubt that any method that can potentially produce the identity
transformation under one key can be considered to be ideal.
Producing the identity under some key is an obvious weakness. I don't
care what the chances of it are - if it's /possible/ to hit it, there's
no way you can legitimately call the resulting construction ideal.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Application specific SBoxes in Blowfish?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 15 Jun 2000 16:00:14 GMT
Andru Luvisi <[EMAIL PROTECTED]> wrote:
: "Sam Simpson" <[EMAIL PROTECTED]> writes:
: [snip]
:> My aim is to have a new version of Blowfish totally incompatible with
:> existing implementations....
: I wouldn't expect that there would be any problems, but why?
Possibility of existence of off-the-shelf Blowfish cracking machine?
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Reply-To: [EMAIL PROTECTED]
Date: Thu, 15 Jun 2000 16:09:44 GMT
lordcow77 <[EMAIL PROTECTED]> wrote:
: Essentially, the existence of exploitable cycles in BBS would
: neccesarily lead to an efficient algorithm for decomposing RSA
: moduli into primes. As such, if you believe that the factoring
: of numbers in that range is a difficult problem, you need not
: loose sleep over the miniscule probability that you will land in
: a short cycle. [...]
It's not a simply a case of losing sleep - it's a case of knowing
whether your system is secure.
Short cycles are weak and insecure - no matter what the probability of
their arising is.
If you're using a system with short cycles in it, do you lose sleep over it?
That depends on the relationship of the chance of such cycles arising and
how much the privacy of your data is worth to you.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: salt length?
Date: Thu, 15 Jun 2000 16:24:11 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> In article <8iarid$u33$[EMAIL PROTECTED]>, zapzing <zapzing@my-
> deja.com> wrote:
> >In article <8iak3p$4ejql$[EMAIL PROTECTED]>,
> > "Elros" <[EMAIL PROTECTED]> wrote:
> >> For use with a stream cipher (e.g. RC4), what's a good length
> for a
> >salt (S)
> >> that gets concatenated (&) to the user supplied key (U)
> before S & U
> >gets
> >> fed into the cipher?
> >
> >I would suggest that the salt be as long as the key.
> >You should not catenate, you should xor instead. The
> >user supplied key should therefore be as long as
> >the steam cipher key also.
(Sorry I just reread RC4 and catenation
would be a great idea. I was confusing it
with something else. The length of the
userkey and the salt should all be
such that a brute forcesearch is impossible,
128 bits say.)
> This will overcome the case of ascii derived swapping in RC4 but
> it will not overcome the fact that if I find the key for one
> message I have the key for all messages. Again I recommend a
> hash for this purpose.
But I don't see that a hash will overcome this
problem either. You have to change the salt or
the hash doesn't change either, right?
> And if the user supplied key (password) is randomly distributed
> among the values 32..127, 12 chars will give you a 96 bit key
> and 15 chars will give you a 99 bit key. If you can remember 15
> char passwords that are fairly random then you are set.
>
> Of course passwords like "th^1N<*(A~hj$.l" are easy to
> remember... hehehe..
>
> Tom
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion
Network *
> The fastest and easiest way to search and participate in Usenet -
Free!
>
>
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "donoli" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Subject: Re: Evidence Eliminator Dis-Information Center
Date: Thu, 15 Jun 2000 16:38:33 GMT
EE Detractor wrote in message ...
>On Tue, 13 Jun 2000 01:37:00 GMT, "donoli" <[EMAIL PROTECTED]>
>wrote:
>
>>IMO the EEsupport guy is a rookie. As I said before he's trying to put
out
>>the fire w/ gasoline. Every time he posts he looses another potential
>>customer.
>
>Rather than merely disrupting the newsgroup, his goal is apparently to
>increase sales by snagging the constant influx of newcomers. He's not
>your typical troll but a spammer who trolls to advertise his product
>and make money. Keeping quiet, as we would with a normal troll, only
>works in his favor by letting him pitch his product without challenge.
>
>
############
I really don't see how he is increasing sales, not he way he presents his
argument.
donoli.
############
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Why the golden ratio?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 15 Jun 2000 16:27:35 GMT
[EMAIL PROTECTED] wrote:
: Like another poster, at first I thought you had misremembered Euler's
: famous formula, [...] However, there is a formula like what you have
: mentioned: it isn't all that simple, and it is due to Srinavasa Ramanujan...
: and you can find it at
: http://mathworld.wolfram.com/GoldenRatio.html
As you say, "it isn't all that simple".
Compare: "AFAIK there is a simple equation of pi, e, the golden number,
and 1, I don't remember it exactly but it was really very simple."
With:
1/(sqrt(5)/(1+5^(3/4)(T-1)^5/2 - 1) - T) (e^2PI/sqrt(5)) =
the continued fraction: 1 + e^-2PI
-------------------------------
1 + e^-4PI
---------------------------
1 + e^-6PI
-----------------------
1 + e^-8PI
-------------------
1 + e^-10PI
---------------
1 + e^-12PI
-----------
1 + e^-14PI ...
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ VIPAR GAMMA GUPPY.
------------------------------
From: Lon Willett <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Comments/analysis requested: stream cipher derived from hash function
(SHA-1)
Date: Thu, 15 Jun 2000 16:47:43 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
[snip]
> It would also be possible to add the counter i to the hash input; that
> guarantees an effectively unlimited cycle length.
Good point. Actually, I did have a counter in my design, but I failed
to recognize its importance, and deleted it for the simplified version
that I posted. Thanks for bringing this to my attention. It is not a
trivial element, and I missed this completely.
[snip]
> > H[i+1] may be weak (or zero), or may be known to an adversary,
> > but CAN NOT BE MANIPULATED by the adversary (ideally, of
course,
> > it is none of these things).
>
> It's generally a good idea in RNG design to assume that the entropy
input
> *could* be manipulated, at least partially.
Actually, looking again, that restriction on the H[] values can be
removed. It was added in an earlier draft, when it was true. But as it
stands here, an attacker can't do anything useful by manipulating them.
The intent of the distinct handling of the hardware RNG output from
other sources of entropy is that if you have a properly functioning
"true" RNG, then the result is also (provably and obviously) a
"true" RNG. But some people are paranoid, and I want this to be a
strong PRNG even should the hardware RNG be sabotaged.
[snip]
> I'd change that to:
[snip]
> I removed the XOR of the output with H[i+1], because it allows state
> following attacks (what you called iterative guessing attacks above)
if
> each H value is of low entropy, and all E values are of zero entropy.
> If you're concerned with this type of attack, it's better to mix in
> entropy only in fairly large chunks.
Good point. But a very tricky situation, and I'm not sure that I got it
wrong. In order to know how many "H" values one should collect before
mixing them in, one has to have a reasonable estimate of the entropy
that they contain. If the hardware RNG is working correctly, then my
approach is fine. If it is defective or sabotaged, how can one estimate
the entropy they contain? The safest assumption is that they contain
zero entropy. And in that case, nothing is lost by mixing them in
immediately.
So, did that make sense (or have I lost myself in my twisted logic)?
> David Hopwood <[EMAIL PROTECTED]>
Thanks for the excellant suggestions!
/Lon
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: quantum cryptography at nytimes.com
Date: Thu, 15 Jun 2000 10:01:43 -0700
"Douglas A. Gwyn" wrote:
> > ... I must say I find it hard to imagine QC replacing
> > very much conventional encryption anytime soon.
>
> Due to the expense, the initial applications of quantum
> cryptography are likely to be those for which guaranteed
> secrecy is crucial.
Even if QC were totally free, who would use it?
The problem is that there is no "guaranteed secrecy".
The various QC security claims are based on idealized
systems. A practical QC system is likely to have no
more security than a conventional one.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Onefish (Twofishes sibbling)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 15 Jun 2000 16:51:04 GMT
Dan Day <[EMAIL PROTECTED]> wrote:
: tomstd <[EMAIL PROTECTED]> wrote:
:> Just for fun I designed Onefish [...]
: Okay, how long until Redfish and Bluefish come along?
http://www.redfishbluefish.com/ already exists ;-)
From there to here,
from here to there,
funny things
are everywhere.
One fish two fish
red fish blue fish.
Black fish blue fish
old fish new fish.
[for the rest, see http://members.aol.com/smargolin/ryan/onefish.htm]
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ UART what UEAT.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: quantum cryptography at nytimes.com
Date: Thu, 15 Jun 2000 10:07:50 -0700
Tim Tyler wrote:
> : So they want to use quantum crypto to generate a random key,
> : and then use it as a pure OTP. Dumb idea, and it will never
> : happen. Banks would be better of sticking with (single) DES.
>
> Hmm. *Perhaps* if the banks are in orbit, something like this /might/
> happen eventually. I must say I find it hard to imagine QC replacing
> very much conventional encryption anytime soon.
Even if the banks were in orbit, I expect they would want better
authentication than QC can provide; want to transmit data much
faster than they can generate key bits; tie it into conventional
networks without decrypting and re-encrypting; not want to
separately manage all those key bits; etc.
------------------------------
** 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
******************************
