Cryptography-Digest Digest #495, Volume #9 Mon, 3 May 99 15:13:03 EDT
Contents:
Re: Fast random number generator (Mok-Kong Shen)
Re: Stream Ciphers and Quantum Computer Resistance ([EMAIL PROTECTED])
Adi Shamir ("Jung-Mok Hwang")
Re: Stream Ciphers and Quantum Computer Resistance (John Savard)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
Re: Scramdisk 2.02h + Win98 = Can't shutdown to DOS. (Shaun Hollingworth)
Re: mcrypt again ([EMAIL PROTECTED])
Re: Fast random number generator (John Savard)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Fast random number generator
Date: Mon, 03 May 1999 18:57:01 +0200
[EMAIL PROTECTED] wrote:
>
>
> Also given a deck of m n-bit words does anyone know a good shuffle algorithm?
> Also a key-init shuffle like RC4?
What is your criteria of 'goodness' of a shuffling algorithm?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Stream Ciphers and Quantum Computer Resistance
Date: 3 May 1999 18:14:57 GMT
Reply-To: [EMAIL PROTECTED]
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> writes:
>In article <7gj2tp$1b3o$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
>> SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> writes:
>> > Actually if one wants quantum computer resistance one should not be
>> >so worried about reversiblity.
>>
>> Your ignorance is astonishing. Reversibility is very important since
>> there is a space trade-off in making an irreversible algorithm reversible.
>> This space trade-off could dramatically increase the number of quantum
>> bits and gates necessary to impliment an algorithm on a quantum computer
>> and could thereby hinder the ability to crack an algorithm on a
>> quantum computer.
>>
>
> I guess a simple proof that some one of your limited mentaly ability
>could under stand is this. If one encrypted with a incredable complex
>method that only had a key of 2 bits. Then the quantum compter needs
>to only test 4 cases max no matter how comples the encryption was.
>It is the entropy that is the main key to preventing quantum computers
>of the future from being able to be CRACKED period. Or is this over your
>head?
Gee, a 2-bit key is such a realistic example. How, exactly does this
apply to 256-bit keys, where there are 2^256 keys instead of 4 and where
it will take a QC on the order of 2^128 clock cycles to crack, which is
about 10^38, which if you've got a GHz quantum computer is 10^29 sec which
is about 3 x 10^21 years. Take 3 orders of magnitude for a massively
parallel QC and another 3 orders of magnitude for a THz QC and you're
still at 3 x 10^15 years. If you can get a 5 order of magnitude improvement
over a "1000 CPU" THz QC (100,000 machines participating in
www.quantum-distributed.net?) then you can start talking about brute
force cracks on the order of the age of the universe.
>> > But one should worry more about the
>> >overall entropy of the system. If one is limited by using a weak method
>> >such as any of the AES canditates likely to be blessed by the NSA and
>> >if one is sending ascii messaages of a few dozen characters or more
>> >then quantum computers will be able to solve for the likely unique
>> >solution.
>>
>> Oh really? Give us a proof.
>
> I did but it may be to complex for you.
No, you didn't give a proof.
>> Quantum computers do not "settle down" on the correct solution. And I'm
>> not aware of an analysis of an extension of the quantum search algorithm
>> to the case where there is more than one solution -- if you have one and
>> it shows that it dramatically decreases the effectiveness of the quantum
>> search algorithm, then I suggest that you post your reference.
>
> If you read some of the literature from 1997 you can see that the
>advantage of quantum compters is that they can try more than one
>solution at a time. I word things the way I want to if you want to
>word differently do so.
It doesn't matter how you "word" things, the fact of the matter is that
quantum parallelism does not give you the ability to run every solution
at the same time and get an instant answer. Quantum computers are not
magic. Unfortunately, they aren't the holy grail of code cracking which
will render all the AES candidates crap and force the world to use
SCOTT19U.ZIP. Nice fantasy, but I'm afraid that you've forgotten to take
your lithium again today.
>But only a fool would think that research
>since then has not gone BLACK and that the NSA does not already have
>very cool quatum compters that you may lack the mental ability to
>understand.
Even assuming this, they are still bound by the laws of physics. And it is
provable that the best algorithmic improvement that you can get from a brute-
force search is sqrt(N). That means that you need to double the keysize
(if you assume that you could even build a quantum computer that ran as fast
as a classical one). And thanks to powers-of-2, that means that 256-bit
key crypto is going to be secure for one hell of a long time.
>That is why the key to future encryption methods should
>greatly consider entropy as a major part of the design. So that there
>is enough entropy in messages so that many keys can decrypt
>to more than one message. Thus making it unlikely that a gussessed
>key even if it gives a correct looking message would actually be the
>right message.
So, even if it's the wrong message, it is unlikely that it'll be
intelligible and you can just keep on cracking until you find the key that
makes sense. You haven't shown that having more than one solution to
the search problem makes a QC any less efficient.
--
Lamont Granquist ([EMAIL PROTECTED])
ICBM: 47 39'23"N 122 18'19"W
------------------------------
From: "Jung-Mok Hwang" <[EMAIL PROTECTED]>
Crossposted-To: de.org.ccc
Subject: Adi Shamir
Date: Mon, 3 May 1999 19:40:21 +0200
Hi!!!
Did anybody of you hear anything about Adi Shamirs new invention?
He published his new "decipher-device" last week.
With the help of Shamirs technology, it must be possible to shorten an coded message,
so that it is easier to encode the message....
Couldnt get more information about this....
Would be very nice if somebody could sent me further details....
thanx in advance....
-Jung-Mok
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Stream Ciphers and Quantum Computer Resistance
Date: Mon, 03 May 1999 17:38:03 GMT
I recieved by E-mail a reply to my posting that was very interesting and
informative. Since the author said "Feel free to repost this to sci.crypt",
I think that I should do so, because this item may well be found helpful by
many:
<begin E-mail>
Hi, I've just completed a PhD thesis on reversible computing at MIT, so you
might consider me qualified to answer your question.
> From: [EMAIL PROTECTED] ()
> Newsgroups: sci.crypt Subject: Stream Ciphers and Quantum Computer
> Resistance Date: 2 May 99 03:33:30 GMT Organization: Edmonton
> Community Network Message-ID: <[EMAIL PROTECTED]>
>
> Having noted that at least *one* view of quantum computers envisages
them
> also incorporating reversible computation, in order that they can avoid
> catastrophic heat buildup while isolated,
Actually, my understanding is that pretty much *all* the quantum computing
schemes are reversible. The essential primitives in quantum computing are
unitary transforms (multiplications by a matrix whose inverse equals its
conjugate transpose), and these are invertible operations. It's been shown
that irreversible measurement operations are not strictly necessary in any
quantum algorithm until the final (readout) stage. I can find you the
reference for that result if you need it.
> it occurs to me that one can certainly design a cipher so that it causes
> headaches for a reversible computer.
>
> A long sequence of irreversible operations - operations that can be done
> reversibly, but which use up blank storage - would help.
>
> Of course, in some cases, one can reverse a calculation after copying
its
> result, so this is still oversimplified. But if one keeps needing new
> results, and therefore the only way everything could be cleaned up is if
> everything is kept around till the end, there is still a problem:
> doubtless, quantum computer experts already know how to state the
precise
> limitation here.
These issues have been fairly well explored. There is an algorithm by
Bennett (1989) (see my thesis bibliography) that can simulate an arbitrary
irreversible machine reversibly with only time O(T^(1+epsilon)) and space
O(S log T) in the original time T and space S of the irreversible
computation. Epsilon can be reasonably small, so that the asymptotic time
increase is not very great.
Also, linear-time simulations are possible with only O(S T^epsilon) space.
Further, for many problems, even more efficient reversible algorithms are
possible, that require either *no* more time or space asymptotically, or
more by only logarithmic factors. It would be interesting to work through
your crypto algorithms and see if any of them fall into this category.
However, anything that works by iterating a one-way function is probably
not going to have a reversible algorithm that's any better than Bennett's
general approach. Section 3.4 of my thesis comes close to proving this
rigorously.
You can read lots of details on all these issues in chapters 3 and 9 of my
thesis, which is on the web at
http://www.ai.mit.edu/~mpf/thesis/phdthesis.html.
Hope this helps,
-Mike Frank
P.S. Feel free to repost this to sci.crypt.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Mon, 03 May 1999 18:43:53 GMT
On Mon, 03 May 1999 09:45:01 GMT, in
<7gjr6t$im9$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] wrote:
>Terry Ritter wrote:
>[...]
>[...]
>Use of a different cipher for each compartment would make
>some sense. The intelligence value of messages would be
>somewhat partitioned among the ciphers. That is not the
>scheme you proposed.
I note that if your interest was in getting a good design, you would
be promoting your scheme as "better." You are not.
I proposed using a different cipher for each message. That is
*superior* to having a different cipher for each intelligence
compartment. But no sort of compartmentalization will by itself solve
all security problems.
>Your opener "as far as I know" is kind of a giveaway.
The only "giveaway" here is that I am not inside the security
community. That is no surprise. But I doubt anyone questions that
compartmentalization is in fact used in practice.
>If
>you knew in detail how classified systems work, you would
>not be allowed to post it here. Since you don't, I suggest
>you not try to serve a market you know little about.
What kind of argument is that?
If I knew current development from the inside, how could I develop
improvements for the outside? My stuff is not for "classified
systems," it is for ordinary cipher users.
The use of randomly-selected ciphers on a per-message basis closes a
fundamental security hole in ciphering. That hole is the fact that
some attacks expose not just the current message, but almost any
message ever sent. And we cannot know when such an attack exists, or
is being applied. The absolute *best* we can do is to terminate any
such attack by moving on to other ciphers.
>[...]
>And that's where your system fails - real world projects
>have no such "each piece of information should be in only
>one message" rule. Are there projects in which the key
>documents do not go through many revisions?
Any failure that "my system" experiences is at least bounded by the
limits of a message, or even multiple messages for multiple breaks.
When we use a single cipher, there is no such bound.
However, it may be that projects of highest security should transmit
only changes to any plan. These would be "updates" instead of
"replacements," the way software is sometimes changed.
>Where the
>information any pair of users shares is disjoint from what
>any other pair shares?
Sure. It is called working independently. As far as I know, this is
in fact used in the highest security projects.
>[...]
>> The argument that automatic compartmentalization is useless parallels
>> the argument that cryptography itself is useless, and is similarly
>> meaningless: Since users do disclose secrets, and cryptography cannot
>> enforce this, so cryptography must be useless; and with automatic
>> compartmentalization, since users do put a range of data in a message,
>> if that message is exposed, all the information is exposed, so
>> compartmentalization must be useless.
>
>No such argument appeared.
It is perfectly reasonable to demonstrate false logic by showing that
a similar construction implies false results.
>You also have the flaw backwards;
>the real problem is not one message carrying a great deal of
>intelligence, but that many messages carry the same intelligence.
>That intelligence is available to an attacker that can read just
>one of the messages carrying it.
The flaw is what it is; the only "backwards" thing about it is your
view of it.
Whenever attackers can read a message, they get the contents OF THAT
MESSAGE. Those users who place fewer independent facts per message
thus do risk fewer independent facts when messages are broken. But at
least the user can then continue with their work, automatically using
new ciphers, and having new ideas protected. An attack which broke
one cipher probably will not work on the next cipher, or subsequent
ciphers.
In contrast, for those users who use a single cipher system, a break
of that system also breaks the same system they have been using and
will be using. That one break thus has the possibility of exposing
everything sent on that cipher, past, present, and future.
It seems clear enough that losing the data in a single message is far
better than losing all data over all of time. Certainly users will
change projects: Even exposing the entire current project is far
different than exposing all past and future projects.
>[...]
>> >I think dynamically
>> >choosing ciphers from a large pool is simply naive.
>>
>> But the question is whether you have a factual basis for this opinion,
>> and whether you draw your conclusions from a reasoned argument. None
>> of that is given here.
>
>Wrong. The premise was clearly stated: that in real world projects
>and in real world enterprises, the same intelligence is carried in
>many messages. No one has disagreed, with the possible exception
>of your conjectures about compartmentalization above.
Compartmentalization is a fact. That real security organizations do
use compartmentalization is a fact. The only "conjecture" here is
that I cannot personally testify to that from current experience. But
"no one has disagreed" with me about that, with the possible exception
of your handwaving which is apparently based on no facts at all.
>I showed how
>the conclusion follows from the premise, and if you doubt the
>premise you have only to look at real world projects, read texts on
>project management, or look at how the information systems that
>support team projects work.
The compartmentalized system can be attacked and exposed message by
message. But a break only exposes the information in one message.
And if that message does not in fact contain "all" information
protected by the system over time, then that break does not expose
"all" information.
But when a single cipher system is broken, that one break may expose
all information over all time. This is why we do not want to use a
single cipher system.
>[...]
>> The argument against having many ciphers presumably rests upon the
>> supposed "strength" of the single cipher we would use instead.
>
>Not really. Only in that we are more likely to be able to
>choose one cipher that is secure, than to choose a thousand all
>of which are secure.
That's an interesting point. The problem is that we *cannot* *know*
that the one cipher we choose really is permanently secure. We may
not choose wisely. And by this one choice we risk all of the
information we ever send.
If that cipher is ever broken by our Opponents, we will not know. We
will still be telling everyone around us how secure our system "must"
be, because all "our" experts could not break it when they tried. We
will continue to use a broken system.
When we have only one cipher, we need no protocol for changing
ciphers. So when someone finally stumbles over the fact that the
cipher is compromised, cipher change will be an ordeal. But when we
normally change ciphers every day, eliminating a particular cipher
from the mix is trivial.
>> But if we multi-cipher, any particular cipher we think strong can be
>[...]
>> What is there to not like?
>
>As noted, I have not here argued against multiple encryption.
>The subject here is the per-message random choice of ciphers.
With "PMRC" a break exposes the content of one message. If we assume
that some of the ciphers are weaker than one we would have chosen, we
may lose the contents of several messages. That is unfortunate, but
we can continue our work.
Without PMRC, a break potentially exposes all information over all
time. Everything we have done and everything we will do continues to
be exposed. This is the Achilles' heal of current ciphering practice,
and we must act to change it.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Shaun Hollingworth)
Subject: Re: Scramdisk 2.02h + Win98 = Can't shutdown to DOS.
Date: 3 May 1999 12:20:25 -0500
On Tue, 27 Apr 1999 22:20:57 GMT, [EMAIL PROTECTED]
wrote:
>All,
>
> I have just replaced scamdisk 2.02c with 2.02h. Now I find
>that after using Scramdisk I cannot "restart in MS DOS mode." The
>screen goes black as normal, but instead of processing the
>autoexec.bat it just hangs, with the cursor flicking in the top left
>hand corner.
> I know this problem is the rusult of the new Scramdisk. I can
>do anything else, and restart in dos works fine. However, after a
>fresh boot, if the first and only thing I do is open Scramdisk, then
>close it again (I don't even have to open a container), "restart in
>Dos" hangs.
> Has anyone else experienced similar? Does anyone have any
>suggestions other than going back to 2.02c?
>
>Thanks for your time,
Make sure [ ] disable fast shutdown is UNCHECKED in
msconfig (Run 'msconfig' at the RUN option on the start menu) and make
sure that the fast shutdown config option is enabled in scramdisk
configure....
Regards,
Shaun.
>
>JP.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: mcrypt again
Date: Mon, 03 May 1999 17:52:24 GMT
> /* perform data dependant rotations */
> for (a = 0; passwd[a]; a++)
> key[a & 1] = key[!(a & 1)] ^ rol(key[a & 1], ((passwd[a] - passwd[a - 1]) &
> 15));
> }
Oops sorry,that should be '& 31' not & 15... both will work (15 did in my
tests...)
Tom
>
> The last line is rather wierd, but the for loop applies to the line(s). It
> generates completely different outputs when one char is different. It will
> suffice for passwd mushing I think. BTW, the output is 64 bits, but the
> input must be 16 bytes, you can pad if you need to, but I wouldn't recommend
> passwords under 16 bytes anyways.
>
> --
> PGP public keys. SPARE key is for daily work, WORK key is for
> published work. The spare is at
> 'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
> 'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
>
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Fast random number generator
Date: Mon, 03 May 1999 18:54:18 GMT
[EMAIL PROTECTED] wrote, in part:
>Also given a deck of m n-bit words does anyone know a good shuffle algorithm?
Depends what you mean by good.
If one uses a generator of good random numbers much larger than m, one can of
course use the classical shuffle algorithm to guarantee that all shuffles are
equally likely:
bottom = m ;
choices = m ;
For top = 1 to m-1 :
{ choose a random number, N, between 1 and choices;
if N is not equal to 1 :
{ swap List(top) and List(top+N-1) ;
}
}
When one is generating random integers from 1 to m, though, then if one wants
a good shuffle though not necessarily a perfect one, one has to fiddle around
a bit. Running RC4 for a while is, I suppose, one way to do it.
In my block ciphers Quadibloc II and Quadibloc III, I used a scheme which
satisfied me, after I couldn't find anything out there that I liked. Maybe
the method I use in them will appeal to you as well, although it's somewhat
elaborate.
To complement the English-language description of the method I use on my web
site, at
http://members.xoom.com/quadibloc/co040705.htm
here's some pseudocode for the same method. This just shows the method I use
to generate one permutation: I generate S-box S8 by generating three of these
permutations, thus ensuring near-perfect randomness.
USED, UNUSED, and EMPTY are flags, -1 can be used for them, so they won't
conflict with the numbers also stored in these arrays.
* Initialize arrays
SourceNumbers[0..255] = 0..255 ;
ShuffledResult[0..255] = UNUSED ;
Duplicates[0..255] = EMPTY ;
DuplicatePonter = 0 ;
* First phase: ShuffledResult is to be largely identical to the
* first 256 random numbers, except that it can't have any number
* appearing in it twice. So, try to fill it from those numbers
* as far as possible.
For counter = 0 to 255 :
{ choose a random number, N, between 0 and 255 ;
if SourceNumbers[ N ] = USED :
{ Duplicates[ DuplicatePointer ] = N ;
increment DuplicatePointer ;
}
else
{ SourceNumbers[ N ] = USED ;
ShuffledResult[ counter ] = N ;
}
}
* Now, see how many duplicates there were in the first 256 random numbers.
* If there were 2 or fewer, proceed immediately to generating the final
* random shuffle.
If DuplicatePointer = 0 :
{ return ShuffledResult ;
}
If DuplicatePointer = 1 :
{ counter1 = 0 ;
while ( ShuffledResult[ counter1 ] is not equal to UNUSED )
{ increment counter1 ;
}
counter2 = 0 ;
while ( SourceNumbers[ counter2 ] = USED )
{ increment counter2 ;
}
ShuffledResult[ counter1 ] = SourceNumbers[ counter2 ] ;
return ShuffledResult ;
}
If DuplicatePointer = 2 :
{ if Duplicates[0] is even :
{ counter1 = 0 ;
while ( ShuffledResult[ counter1 ] is not equal to UNUSED )
{ increment counter1 ;
}
counter2 = 0 ;
while ( SourceNumbers[ counter2 ] = USED )
{ increment counter2 ;
}
ShuffledResult[ counter1 ] = SourceNumbers[ counter2 ] ;
increment counter1 ;
increment counter2 ;
while ( ShuffledResult[ counter1 ] is not equal to UNUSED )
{ increment counter1 ;
}
while ( SourceNumbers[ counter2 ] = USED )
{ increment counter2 ;
}
ShuffledResult[ counter1 ] = SourceNumbers[ counter2 ] ;
return ShuffledResult ;
}
else
{ counter1 = 0 ;
while ( ShuffledResult[ counter1 ] is not equal to UNUSED )
{ increment counter1 ;
}
counter2 = 255 ;
while ( SourceNumbers[ counter2 ] = USED )
{ decrement counter2 ;
}
ShuffledResult[ counter1 ] = SourceNumbers[ counter2 ] ;
increment counter1 ;
decrement counter2 ;
while ( ShuffledResult[ counter1 ] is not equal to UNUSED )
{ increment counter1 ;
}
while ( SourceNumbers[ counter2 ] = USED )
{ decrement counter2 ;
}
ShuffledResult[ counter1 ] = SourceNumbers[ counter2 ] ;
return ShuffledResult ;
}
}
* If we haven't left, we have more than two duplicates, so we must
* perform the second pass.
* First, pad out the array of duplicates to fill it, if
* required.
If DuplicatePointer < 255 :
{ sourcecounter = 0 ;
sourcelimit = DuplicatePointer ;
For fillcounter = DuplicatePointer + 1 to 255 :
{ Duplicates[ fillcounter ] = Duplicates[ sourcecounter ] ;
increment sourcecounter ;
if sourcecounter > sourcelimit :
{ sourcecounter = 0 ;
}
}
}
* Then, randomize it with an additional 256 random bytes.
For counter = 0 to 255 :
{ Choose a random number, N, between 0 and 255 ;
Duplicates[ counter ] = N xor Duplicates[ counter ] ;
}
* Take the array of unused byte values, and shuffle it with
* random swaps.
For counter = 0 to 255 :
{ pointer = Duplicates[ counter ] ;
if counter is not equal to pointer :
{ swap SourceNumbers[ counter ] and SourceNumbers[ pointer ] ;
}
}
* First, try filling the empty spots in the result array from
* byte values in corresponding positions.
For counter = 0 to 255 :
{ if ShuffledResult[ counter ] = UNUSED :
{ if SourceNumbers[ counter ] is not equal to USED :
{ ShuffledResult[ counter ] = SourceNumbers[ counter ] ;
SourceNumbers[ counter ] = USED ;
}
}
}
* Then, finally, fill all the remaining empty spots from the
* remaining shuffled byte values.
sourcepointer = 0 ;
resultpointer = 0 ;
finished = FALSE ;
while not finished :
{ while (not finished) and (SourceNumbers[ sourcepointer ] = USED) :
{ increment sourcepointer ;
if sourcepointer > 255 :
{ finished = TRUE ;
}
}
if not finished :
{ while ShuffledResult[ resultpointer ] = UNUSED :
{ increment resultpointer ;
}
ShuffledResult[ resultpointer ] = SourceNumbers[ sourcepointer ] ;
increment sourcepointer ;
increment resultpointer ;
if sourcepointer > 255 :
{ finished = TRUE ;
}
}
}
return ShuffledResult ;
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
** 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
******************************
