Cryptography-Digest Digest #765, Volume #9 Thu, 24 Jun 99 23:13:02 EDT
Contents:
Re: one time pad (AllanW)
Re: Is DES easy to crack whit other kind of attack? (Bill Unruh)
Re: one time pad (Jim Felling)
Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length? ("Michael
Scott")
Re: Is DES easy to crack whit other kind of attack? (infinitySquared)
The Constrained One-Time Pad and the Cryptanalyst's Lucky Day (John Savard)
Re: Encryptor that fits on a disk? (fungus)
Re: one time pad (Jim Felling)
Re: RC4 Susectability (fungus)
Dundee Society (Jim Gillogly)
Description of the scottNNu algorithms..... (Anonymous)
Re: card shuffling related to rc4? (Jayant Shukla)
----------------------------------------------------------------------------
From: AllanW <[EMAIL PROTECTED]>
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 23:37:43 GMT
[EMAIL PROTECTED] (Terry Ritter) wrote:
> One approach to a solution might be to build a physically-random
> device which cannot be incorrectly built, cannot fail to perform,
> cannot be damaged in an undetectable way, and will meet every
> possible test for randomness, even if we have not yet defined
> those tests. Then we could say that our device was "provably
> random," which would imply a security proof for an OTP using
> such a device as a keystream generator. In my opinion, any
> attempt to build such a device would be a foolish quest.
Would it?
Consider a CPU which has no fixed clock speed. That is, instead
of (say) 450MHz, we allow the clock speed to "drift" very
slowly -- sometimes as low as 400MHz, other times as high as
450MHz, in a cycle that repeats 100 times per second.
To this we attach a single-bit counter attached to it's own
clock source, independant of the CPU and much faster. Give
the counter a known duty cycle; ideally, 50% of the time it
contains "0" and the other 50% of the time it contains a
"1". (Other duty cycles can be adjusted algorithmically.)
Like the CPU's clock, we will allow the counter's clock to
"drift", sometimes as low as 3GHz, other times as high as
4GHz, in a cycle that repeats 500 times per second.
Note that the CPU's clock drift is not connected to the
counter's clock drift in any way.
Even when the CPU is at it's fastest (450MHz) and the counter
is at it's slowest (3GHz), the counter will change states
many times during one CPU clock. So the value retrieved by
the CPU during any one poll depends on the exact timing of
the polling pulse. By giving the two clocks different speeds
and having each of them drift, the timing will vary each time
that the CPU polls the counter. If the result of one such
poll is truely random and has a 50% duty cycle, then the
results of N polls should be enough to create a truely-
random N-bit integer.
> On the other hand, I am willing to believe that a well-designed,
> well-constructed, and well-tested physically-random RNG could be very
> secure indeed. The difference is that we have no absolute *proof*.
> And that places the OTP firmly into the body of ciphers we know.
I don't claim to have proven that my device is truely random.
But it does seem to me that it should be possible to
mathematically prove (or disprove) it.
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Is DES easy to crack whit other kind of attack?
Date: 24 Jun 1999 23:21:05 GMT
><[EMAIL PROTECTED]> wrote in message news:7kd7mn$e48$[EMAIL PROTECTED]...
>> Im reading about DES and the possibles attacks. Well at this time DES was
>> cracked by EFF whit a $250.000 craker hardware. But all docs I found is
>about
>> crack the key when u dont know the text. *Im wondering if in a simple PC
actually this is not true. If you know nothing about the text, it is
impossible to crack any crypto system, there is nothing to indicate when
you have found the valid text and when you have garbage. Thus, you have
to know something about the text (eg that it is ascii text) in order to
crack it (ie find the key). The more you know, the better.
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 19:49:22 -0500
Well said. This is exactly the argument against filtering. This belongs in a
FAQ or on a website somewhere. Very succinct, very well stated argument.
The only possible rational reason to play with your RNG's output is if there
is some "brokenness" in your RNG -- short circuit, coupling between
components, etc. and that should be remedied by replacing your RNG with a new
(and in theory fully functional) RNG.
This belongs in a FAQ or on a website somewhere.
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Why Elliptic Curve Cryptosystem is stronger with shorter key length?
Date: Fri, 25 Jun 1999 01:02:40 +0100
Robert Harley <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> Michael Scott writes:
> > See ftp://ftp.compapp.dcu.ie/pub/crypto/schoof.exe. [...]
> > Source code at the same site. Its not as fast as one would like [...]
>
> Yes, I am aware of your program! It is great that something is
> available, but it is not nearly enough to really solve the problem, IMO.
>
> Ideally one would like to pick a size like 256 bits or 400 or
> whatever, and run through a bunch of random curves of that size until
> one (or its quadratic twist) has almost prime order, and do so in a
> reasonable amount of time.
Well to an extent you can do that. In fact prime order seems to be
preferable, and the program supports a search option which searches for that
condition, incrementing the curve B parameter at each step. Fortunately
Schoof's algorithm naturally supports an "early abort " mechanism that
quickly detects curves of non prime order, that is that are divisible by a
small factor, so the search is faster than you might think. Finding a random
curve of up to 256 bits is feasible on your standard home computer, and up
to 400 bits, well I haven't tried that yet, but I suspect that a wet
long-week-end with a lab full of fast PCs might do the trick. In most
applications one trusted and truly random curve is enough.
>It would also be nice to be able to pick
> curves defined over fields of characteristic 2.
>
Indeed it would
Mike Scott
> Bye,
> Rob.
------------------------------
From: infinitySquared <"binthr"@[EMAIL PROTECTED]>
Subject: Re: Is DES easy to crack whit other kind of attack?
Date: Fri, 25 Jun 1999 04:33:07 +0100
actually NOTHING is impossible when you really think about it
Bill Unruh wrote:
> ><[EMAIL PROTECTED]> wrote in message news:7kd7mn$e48$[EMAIL PROTECTED]...
> >> Im reading about DES and the possibles attacks. Well at this time DES was
> >> cracked by EFF whit a $250.000 craker hardware. But all docs I found is
> >about
> >> crack the key when u dont know the text. *Im wondering if in a simple PC
>
> actually this is not true. If you know nothing about the text, it is
> impossible to crack any crypto system, there is nothing to indicate when
> you have found the valid text and when you have garbage. Thus, you have
> to know something about the text (eg that it is ascii text) in order to
> crack it (ie find the key). The more you know, the better.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: The Constrained One-Time Pad and the Cryptanalyst's Lucky Day
Date: Fri, 25 Jun 1999 00:43:53 GMT
In a recent post, Terry Ritter used a novel argument to show that even
the one-time-pad is not provably secure, and that excluding "obviously
weak" output from a true random number generator would not change
this.
For any given pad of true random numbers, one can't prove that it
doesn't correspond to the output of a stream cipher that the
cryptanalyst one is facing might solve!
Well, I demolished his argument (as I understood it) by noting that if
the number of possible messages is N, the probability of this
happening is 1/N the probability of the cryptanalyst obtaining a false
plaintext this way: hence, nothing has happened to reduce uncertainty
concerning the plaintext.
But if we assume that our messages are under attack this way, and if
it is the case that if a cryptanalyst, even without *logical* reasons
to do so (since with a true OTP, there is no *valid* way to infer a
particular plaintext) guesses the correct plaintext, this would lead
to catastrophic consequences...
then, not only _should_ we omit using true random generator output
that is all zeroes, or that corresponds to some simple, regular
sequence that the cryptanalyst would, as it were, accidentally solve,
but when choosing which leaf from our OTP to apply to a particular
plaintext, we should then take the trial ciphertext, and subject it to
some sort of "standard" analysis suite...and reject it if a plaintext,
even the wrong one, turns up (first among plausible ones) that would
put the attacker on the right track instead of misleading him!
The basic idea is that if the cryptanalyst has good luck 1/N of the
time, we should try to omit these cases. Actually, of course, the
probability of this kind of thing happening is vanishingly small; but
therefore, if the constraint on the key sequence is a gentle one
(don't forbid sequences of, say, _five_ zeroes, but do forbid
sequences of, say, 100 zeroes) the compromise of the theoretical
invincibility of the one-time-pad is also small.
This point, however trifling, is worth considering; I believe that
insights are possible that will allow us to retain a true OTP in the
theoretical sense *plus* solving the "practical" problem of zero keys.
On another topic, how might we improve the OTP so that it is also
immune to the "bit-flipping" attack? A random 256-character alphabet
for each byte? Or can we be more efficient?
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/crypto.htm
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Encryptor that fits on a disk?
Date: Fri, 25 Jun 1999 03:57:23 +0200
[EMAIL PROTECTED] wrote:
>
> Hello,
>
> I am looking for an encryptor that could be used from a single floppy
> disk. I wish I could use PGP but unfortunatly its just to big.. plus
> the system I am working on gives me limited admin.. no installs
> basicaly. I remember seeing once a program that did a number of
> algorithms and had high bit keys.. but I forgot the name.. If you know
> of one.. that fits my bill.. please let me know.. Thanks
>
Try this for a simple file encryptor:
http://www.artlum.com/pub.crypt.zip
It's based on RC4 and the passphrase can be as long as you want.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: one time pad
Date: Thu, 24 Jun 1999 19:56:54 -0500
AllanW wrote:
> [EMAIL PROTECTED] (Terry Ritter) wrote:
> > One approach to a solution might be to build a physically-random
> > device which cannot be incorrectly built, cannot fail to perform,
> > cannot be damaged in an undetectable way, and will meet every
> > possible test for randomness, even if we have not yet defined
> > those tests. Then we could say that our device was "provably
> > random," which would imply a security proof for an OTP using
> > such a device as a keystream generator. In my opinion, any
> > attempt to build such a device would be a foolish quest.
>
> Would it?
>
> Consider a CPU which has no fixed clock speed. That is, instead
> of (say) 450MHz, we allow the clock speed to "drift" very
> slowly -- sometimes as low as 400MHz, other times as high as
> 450MHz, in a cycle that repeats 100 times per second.
>
> To this we attach a single-bit counter attached to it's own
> clock source, independant of the CPU and much faster. Give
> the counter a known duty cycle; ideally, 50% of the time it
> contains "0" and the other 50% of the time it contains a
> "1". (Other duty cycles can be adjusted algorithmically.)
> Like the CPU's clock, we will allow the counter's clock to
> "drift", sometimes as low as 3GHz, other times as high as
> 4GHz, in a cycle that repeats 500 times per second.
>
> Note that the CPU's clock drift is not connected to the
> counter's clock drift in any way.
>
> Even when the CPU is at it's fastest (450MHz) and the counter
> is at it's slowest (3GHz), the counter will change states
> many times during one CPU clock. So the value retrieved by
> the CPU during any one poll depends on the exact timing of
> the polling pulse. By giving the two clocks different speeds
> and having each of them drift, the timing will vary each time
> that the CPU polls the counter. If the result of one such
> poll is truely random and has a 50% duty cycle, then the
> results of N polls should be enough to create a truely-
> random N-bit integer.
>
> > On the other hand, I am willing to believe that a well-designed,
> > well-constructed, and well-tested physically-random RNG could be very
> > secure indeed. The difference is that we have no absolute *proof*.
> > And that places the OTP firmly into the body of ciphers we know.
>
> I don't claim to have proven that my device is truely random.
> But it does seem to me that it should be possible to
> mathematically prove (or disprove) it.
It will work as a decent RNG, but not a really good one. The problem is in
frequency locking -- the counter systems need to be very carefully isolated
from each other -- otherwise the possibility of mode locking between the
two oscillators exists.(or between them and some other coupled component.
Be careful of hidden multiplier effects -- i.e. clock A is exactly 8X as
fast as clock B will mean that the 0's will be more common than 1's. There
are other possible problems -- I'd use a radioactive decay based method ALA
hotbits in preference to this method.
>
>
> --
> [EMAIL PROTECTED] is a "Spam Magnet," never read.
> Please reply in newsgroups only, sorry.
>
> Sent via Deja.com http://www.deja.com/
> Share what you know. Learn what you don't.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: RC4 Susectability
Date: Fri, 25 Jun 1999 04:02:33 +0200
[EMAIL PROTECTED] wrote:
>
> Hmm well I am wrong. However my arguement still holds true. Is that
> 36% for the first 256 output? Why only the first 256? (It should be
> the first 210 output because of the feedback). Does the 36% hold for
> all multiples of 256 in the output?
>
No, 36% for the first byte output from the generator.
If I've got a 36% chance of getting one byte of the key, then
that makes the key 0.36*8 = 2.88 bits shorter. Not a massive
amount, but significant for smaller keys.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Dundee Society
Date: Thu, 24 Jun 1999 16:50:57 -0700
"Douglas A. Gwyn" wrote:
> Jim Gillogly wrote:
> > With any luck my Dundee Marmalade crock will be visible next to my
> > elbow. No, I'm not a member of the Dundee Society -- this was a
> > case of "If you buy an outfit you can be a cowboy too."
>
> I suspect you're going to have to explain that (and maybe the outfit
> reference as well) to many of the readers.
I'll explain the "outfit" bit if you'll go into greater detail on Dundee.
The Smothers Brothers, a popular comedy duo of my youth, had a song that
went something like:
As I was out walking in the streets of Laredo,
As I was out walking in Laredo one day,
I spied a young cowboy all dressed in white linen,
Dressed in white linen as cold as the clay.
Tom: "I see by your outfit that you are a cowboy."
Dick: "I see by your outfit that you're a cowboy, too."
Both: "We see by our outfits that we are both cowboys."
Looking at audience: "If you buy an outfit you can be a cowboy too."
> Even though LDC hasn't been with us for many years now, the Dundee
> Society seems to live on, or at least have a room reserved for it --
> there's a pointer sign for it in the HQ cafeteria.
>From stories leaking out of the Fort, it seems that Lambros D. Callimahos,
main author of the indispensible Military Cryptanalytics, was the founder of
the Dundee Society, of which all students of his advanced course were
automatically members. It was named after the James Keiller & Sons Dundee
Orange Marmalade crock in which he kept his pencils; I don't know what it
looked like, since there have been around a dozen styles over the years.
Evidently he was quite eccentric, and perhaps went overboard in doing
more and more detailed background for the Zendian Problem, one of the
primary study sets for the advanced cryptanalysis course. I would guess
it's the same syndrome experienced by serious D&D dungeonmasters. Having
pretty much finished the Zendian Problem, I figured if I were going to be
a serious amateur cryppie, I'd need a Dundee crock... my "outfit", as it
were. E-Bay obliged with an antique one.
More details, please?
--
Jim Gillogly
1 Afterlithe S.R. 1999, 23:37
12.19.6.5.9, 13 Muluc 17 Zotz, First Lord of Night
------------------------------
Date: Fri, 25 Jun 1999 04:06:05 +0200 (CEST)
From: Anonymous <[EMAIL PROTECTED]>
Subject: Description of the scottNNu algorithms.....
This is a generalized description of the 'scott' algorithms, derived
from examination of the source code for scott19u. In this description,
all bits/bytes/blocks read left to right (first to last) starting with
index 1. I may not have it all _exactly_ right, but if not, I'm _very_
close.... Figures would help the explaination, I'm sure, but I still
have a headache from looking at the code.... The code itself, in
addition to being very hard to read, is in many places very inefficient
and sloppy. It may, or may not, be doing exactly what the author intends....
B : block size in bits
S : shift size in bits (0<S<B)
R : number of rounds
E/D : B-bit block encryption/decryption algorithm (note that this is
where the key comes in)
L : Message length in bits
N : number of B-bit blocks in the (padded) message
M : the number of bits needed to pad the message to an even number of
B-bit blocks (B*N=L+M)
P[n] : the nth B-bit block of the plaintext (n ranges from 1 to N
inclusive, with block N possibly partial)
C[n] : likewise for the ciphertext
^ : xor
+/- : addition/subtraction modulo 2**B
****************************************************
Encryption:
****************************************************
Step 1:
'Whiten' the plaintext by P[n]=P[n]^K[n] for n = N through 2 where
K[N]=E(P[1])^E(E(P[1])) and K[n]=E(K[n-1]). Note that the first block
is not changed.
(Perform Steps 2 and 3 R times)
Step 2:
Compute C[n]=E(C[n-1]^P[n]+P[n+1]) for n = 1 through N-1 (in that order)
(When computing C[1], use the last B bits of the unpadded message where
C[0] would be called for)
Step 3:
Finishing up the last partial block is a little tricky. Two cases:
Case A) If M<=S
Step 3A1:
Compute C[N] as in step 2 after appending C[1] and C[2] to the end of
the plaintext to provide P[N] and P[N+1].
Step 3A2:
Append bits M+1 through S of C[1] to the end of the ciphertext. (note
that bits 1 through M are encrypted in C[N])
Case B) If M>S
Step 3B1:
Append the B-P bits of plaintext in P[N] to the end of the ciphertext.
(note that this leaks a few bits of plaintext from one round to the
next)
Step 3B2:
Append the left S bits of C[1] to the ciphertext
Step 4:
Left shift the entire encrypted message by S bits (so that left S bits
of C[1] are discarded), leaving a ciphertext with a length of L bits.
Step 5:
'Whiten' the ciphertext as in step 1
****************************************************
****************************************************
****************************************************
Decryption:
****************************************************
Step 1:
'Whiten' the ciphertext by C[n]=C[n]^K[n] for n = N through 2 where
K[N]=E(C[1])^E(E(C[1])) and K[n-1]=E(K[n]). Note that the first block
is not changed.
Step 2:
Right shift the entire message by S bits. (so that the first S bits of
C[1] are undefined/zero)
(Perform steps 3 and 4 R times)
Step 3 :
Dealing with the last partial block (and reconstructing C[1]) is a
little tricky. Two cases:
Case A) If M<=S
Step 3A1:
Move the last S-M bits of the ciphertext to the bits M+1 through S of
C[1] (partially reconstructing C[1])
Step 3A2:
Compute P[N] as below, using bits M+1 through B of C[1] and bits 1
through M of C[2] for P[N+1]
Step 3A3:
Move the right M bits of P[N] to bits 1 through M of C[1] (completing
reconstruction of C[1])
Case B) If M>S
Step 3B1:
Move the last S bits of the ciphertext to the first S bits of C[1]
(reconstructing C[1])
Step 3B2:
Move the last B-M bits of ciphertext to the first B-M bits of P[N].
Step 4:
Compute P[n]=(D(C[n])-P[n+1])^C[n-1] for n = N-1 through 1 (in that
order) (When computing P[1], use the last B bits of the unpadded
plaintext where C[0] would be called for)
Step 5:
'Whiten' the plaintext as in step 1
****************************************************
****************************************************
For scott19u, B=19, S=9, R=23. The encryption algorithm is a a 19 bit
permutation table with the property that repeated encryption of any
value will cycle through all possible values before returning to the
original ('single cycle'). It seems to be built by shuffling in a
vaguely 'RC4-like' manner (I didn't examine it too closely - it didn't
seem all that interesting). As a minor note, the actual code performs
the S bit shift on a block-by-block basis, rather than all at once as I
described, but as far as the function of the algorithm goes, it's the
same thing. The partial block handling in the round
seems _way_ too messy. I think I would just do the trick (described in
Bruce's book - wonder if David has read it.... ;-) of appending the
last M bits of C[N-1] to the remaining plaintext and encrypting that to
C[N] (and then overwriting the end of C[N-1] partially with C[N]),
followed by a circular shift of the entire ciphertext by S bits to the
left. It would be simpler, and wouldn't have the plaintext leak (in
fact, for cases where there is no padding, this would produce the same
output as the existing code). Also, there's no reason you couldn't do
this with DES, or something else, for the encryption algorithm.
Enjoy. Seek balance.
Ras Algethi
------------------------------
From: [EMAIL PROTECTED] (Jayant Shukla)
Subject: Re: card shuffling related to rc4?
Date: 25 Jun 1999 02:22:33 GMT
John Myre <[EMAIL PROTECTED]> writes:
>[EMAIL PROTECTED] wrote:
>>
>> Eyal Soha wrote:
>> > The RC4 expansion is similar to the shuffling of a deck of cards
>> (128).
>> > So if RC4 has a skew toward some shufflings more than others, then
>> you can
>> > might know in what order to perform a brute-force attack on rc4.
>> Which
>> > makes it weaker, yes?
>>
>> No. The RC4 key schedule uses an 8-bit feedback with 2^8 steps so that
>> each card is shuffled with a random card. The code resembles
>>
><snip>
>I'm sorry, Tom, but Eyal Soha has a point. Not all RC4 shufflings
>are equally likely. You'd have to be a lot smarter than me,
>however, to turn this weakness into an attack. The possible
>number of states of RC4 is so huge that I suspect there is no
>*practical* problem.
Weakness pointed out by Eyal is known. The way he is trying
to exploit the weakness is what we call "differential cryptanalysis".
To get around this weakness, you can either make your round function
more complex or add more rounds. Take your pick. The weakness
pointed out is know and so are the ways to fix it.
The origin of this weakness is that we do not know a function(s)
(or a very small group of functions, say 2-4) that give(s) perfect
"confusion" and "diffusion" in one round (a single application)
and are not too compute intensive. I can go on about this and
cipher design, but it is better if you read some good book.
To learn more about it, one can read "cryptography & network security"
by William Stallings. It is just about the best book on cryptography
I have seen so far. For differential cryptabalysis, read papers
by Biham & Shamir or read their book "Cryptanalysis of the DES".
~Jayant
------------------------------
** 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
******************************
