Cryptography-Digest Digest #39, Volume #14 Thu, 29 Mar 01 19:13:01 EST
Contents:
Re: Encryption of Encrypted Material results in strength??? ("Joseph Ashwood")
Re: Diceware Passwords (Marc)
Re: Encryption of Encrypted Material results in strength??? (Marc)
Re: An extremely difficult (possibly original) cryptogram (daniel mcgrath)
Re: DES key replacement. ("Sam Simpson")
Re: rc4 ([EMAIL PROTECTED])
Re: An extremely difficult (possibly original) cryptogram (Jim Gillogly)
Re: Idea - (LONG) (David Wagner)
Re: DES key replacement. (Mok-Kong Shen)
Re: texts on factoring? (Steve Roberts)
AES - test vectors? (Marc)
Re: TRNG question (Terry Ritter)
Re: rc4 ("Edmond Ho")
Re: Idea - (LONG) ("Douglas A. Gwyn")
Re: Breaking a DES encrypted code. ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Encryption of Encrypted Material results in strength???
Date: Thu, 29 Mar 2001 14:12:37 -0800
Crossposted-To: alt.computer.security
"Bas Bloemsaat" <[EMAIL PROTECTED]> wrote in message
news:9a05kn$sip$[EMAIL PROTECTED]...
> I've read this before, in Applied Cryptography. I wondered, what are
related
> keys?
Related keys are keys that are chosen from each other, or where one may
imply something about the other. Fairly typical of related key ideas is:
#1
Seed Rand
pull key 1 out of rand
pull key 2 out of rand
key 1 and key 2 are related by the random number generator. However if you
seperate the 2 pulls by a reseed the relaionship disappears.
Joe
------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: Re: Diceware Passwords
Date: 29 Mar 2001 22:30:28 GMT
>>Some words on the list have only 1-3 letters, for example "s". Isn't
>>the entropy added by "s" less than 12.9 bits? An attacker who does
>>not follow the Diceware scheme but attacks from another angle (eg
>>brute force) sees the "s" as one letter of 26, not 7776.
>Diceware works on the principle that the words are just a convenient
>mnemonic device for human beings -- the actual randomness comes from
>the dice. The word-list gives us a convenient mapping between those
>numbers and something we can remember.
Thanks for your answer.
Yes, I do understand why the words are _supposed_ to give 12.9 bits
of entropy (because they are chosen among 7776). However, if the
mnemonic in itself is easier to guess than its position in the list, the
attacker might just ignore the passphrase history and attack it like
tradidional passphrases.
Imagine that the words on the list have 8 bits of entropy on average,
viewed under the established common opinion that english words have
only 1-2 bits per letter and that the list is compiled from short
english words.
When I now build a 5 word passphrase from them, I get 5*8 = 40 bits
of entropy. An attacker, performing a 2**40 "english ascii" bruteforce,
will find my passphrase. He simply skips the more complex 2**64.5
"diceware" bruteforce in favor of the simpler one.
The Diceware FAQ recommends to discard passphrases <14 letters in length,
which seems to strengthen my point. Some words are just weaker than
others, and their common property is "being short". Too many weak words,
and you better generate another phrase..
I have the impression that the inventors think there are enough high
entropy words on the list to compensate for the weaker words, and anyway
if a passphrase has 50 bits already who cares if the 5th word adds
3 or 5 or 12.9 bits?
The diceware system IMHO can only guarantee the entropy if I were to
enter the dice'd _numbers_ instead of the mnemonics (eg by looking
up the numbers in a printout that I keep next to the computer).
I don't doubt that diceware phrases are stronger than most phrases
that users come up with traditionally, but I do doubt that they actually
provide the promised entropy of 12.9 bits per word (when generated
with the word list provided by the Diceware web site).
In my opinion each and every word on the list should have an inherent
entropy of 12.9 bits minimum (ignoring the problems of reliably measuring
the entropy of a word). Only this would guarantee that no entropy
is lost in the process of converting the numbers (12.9bit) to words.
Please clarify this for me, I honestly do not know if I am wrong or
Diceware?
------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: Re: Encryption of Encrypted Material results in strength???
Date: 29 Mar 2001 22:34:48 GMT
>> I have been told that encrypting an encrypted message actually
>> decreases the security. I am not a cryptographer, but will accept that
>> on faith.
When encrypting twice were to decrease security, an attacker would not
try to attack a message as it is, but first encrypt it another time (to
decrease its security) and attack it THEN.
Or encrypt it yet another few times to further decrease the security?
This is nonsense. It might be true for some cases that security does
not increase despite the extra keybits and extra computing investment
suggest so, but I doubt that there is actually a DECREASE of security.
------------------------------
From: [EMAIL PROTECTED] (daniel mcgrath)
Crossposted-To: rec.puzzles
Subject: Re: An extremely difficult (possibly original) cryptogram
Date: Thu, 29 Mar 2001 22:42:01 GMT
On Mon, 19 Mar 2001 19:15:12 GMT, [EMAIL PROTECTED] (daniel mcgrath)
wrote:
>Jim Gillogly ([EMAIL PROTECTED]) wrote:
>
>>daniel mcgrath wrote:
>>>
>>> On Thu, 15 Mar 2001 11:43:18 -0800, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>>> >The first hint is consistent with my monome-dinome hypothesis, and the
>>> >second hint could mean something like HTML.
>>>
>>> HTML it is. I thought at the time that telling you that would make it
>>> too easy, but apparently you really want bigger hints.
>>
>>Certainly. As people (including me) keep saying, a very strong
>>algorithm will still be strong even if everything except the key
>>used for that message has been totally exposed. Even if you give
>>away the plaintext to all but the last 10% of a message, this
>>should give the cryptanalyst no help in decrypting the last 10%.
>>A few people enjoy working on ciphertext-only challenges in unknown
>>cipher systems, but for most that gets very old in a hurry.
>>
>>Just to add a little content, here's the sorted dictionary from
>>this, gathered together from my hypotheses with Daniel's
>>confirmations, and from the messages from Henk and Doug:
>>
>>> >6. Daniel gave a big clue, as follows:
>>> >
>>> > You came 620711143 close with 54006 of the 806648
>>> > first hypotheses 711015 you had 450103. The code
>>> > 696690137 used here, 27465680662, is based 7774
>>> > the same 20650362042 idea as 71112 system used
>>> > 1743 my cryptograms.
>>
>>for 1743 (probably)
>>general 20650362042
>>however 27465680662
>>made 450103
>>one 54006
>>rather 620711143
>>system 696690137
>>that 711015
>>the 71112
>>upon 7774
>>very 806648
>
>All of the above equivalences are correct. So have you figured out
>the system? (I think Douglas has it.)
>
>>Note that pieces of words fit into this ordering: the "ther"
>>from "rather" fits in well after "the", the end of "very"
>>(either 6648 or 648) fits after "rather", "tem" may be 690137,
>>the "ver" from "however" fits just before "very", and so on.
>>Given enough of these, one could use one-part code methods
>>even without recovering the actual algorithm used to create
>>the codes. Assuming this property is representative of the
>>actual messages, I'd expect exposing half of the plaintext
>>to make it fairly straightforward to recover the other half.
>>
>>Note that this clue is illustrative only: it demonstrates
>>the encoding idea without giving away the actual system.
>>In particular, 71112 and the longer strings do not appear
>>in the real challenge cryptograms.
>
Jim, Doug -- how are you doing?
==================================================
daniel g. mcgrath
a subscriber to _word ways: the journal of recreational linguistics_
http://www.wordways.com/
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: DES key replacement.
Date: Thu, 29 Mar 2001 23:40:25 +0100
You seemed to have missed the smiley.
The point of the previous post was that a Yaniv posted a harmless question
about DES - and commented on the 64-bit key length. Terry replied 'First, a
DES key is 56 bits, not 64.' and I pointed him towards the NIST FIPS
indicating that his response was technically incorrect.
Is this hard to follow ;) <- Note the smiley again!
--
Regards,
Sam
http://www.scramdisk.clara.net/
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Sam Simpson wrote:
> >
> > Hey, I'm quoting from NIST....What can be a more definitve source? ;)
>
> Frank Gerlach has given the correct explanation. The key
> is 64 bits but you cannot arbitrarily choose these 64 bits.
> You can freely choose only (specific) 58 of them, the
> remaining 8 being parity bits, i.e. dependent on the 58.
> Read the standard document, if you still have doubt about
> this.
>
> M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: rc4
Date: 29 Mar 2001 22:51:40 GMT
Edmond Ho <[EMAIL PROTECTED]> wrote:
> thanks for the information, but i still cannot get the two to be compatible.
> i may just be an doing something very stupid, so i'm going to post what i
> did (keeping in mind i'm a bit new to unix):
> $gcc -o rc4 rc4.c (this is the non-compacted version)
> $gcc -o rc4-2 rc4-2.c (this is the first compacted version)
> $echo test | rc4 1234 | rc4 1234 (this returns "test")
> $echo test | rc4-2 1234 | rc4-2 1234 (this also returns "test")
> $echo test | rc4 1234 | rc4-2 1234 (this should return "test", unless i have
> completely misunderstood how both inplementations of rc4 work)
> hopefully i didn't overlook something obvious. many thanks in advance.
Nope, you didn't miss anything. There's actually a bug in the
"compacted version" that you're using (rc4-2). The bug is in the loop
that looks like this:
c=256;while(p[c]=--c);
Depending on the C compiler, this can legitimately be compiled to do
two quite different things: the c index on the left is either the
original value or the incremented value of c. Apparently
the person who wrote (and presumably tested) this code had a compiler
that did it one way (using the incremented version of c), and your
compiler does it the other way, leading to incompatibilities.
Here's a version that works, by replacing that loop:
#define W(X) 256;h=*(p+X);*(p+X)=*(p+j);*(p+j)=h;/* Use: rc4 hexkey <in >out */
unsigned char s[256],d[512],b[8192],i,j,p[256];int h,n,m;main(int c,char *v[]){
while((m=read(0,b,8192))>0){if(c>1){(n=strlen(strcpy(d,v[1])))&1&&n++&&strcat(d
,"0");n/=2;for(c=0;c<n;c++){*p=d[c*2];p[1]=d[c*2+1];sscanf(p,"%x",&h);s[c]=h;}c
=255;for(;p[c]=c;--c);do{j=(s[i]+p[c]+j)%W(c)i=(i+1)%n;}while(256-++c);for(c=i=j
=0;c<m;c++){j=(p[i=(i+1)%256]+j)%W(i)b[c]^=p[(p[i]+p[j])%256];}}write(1,b,m);}}
That kills the cute property that each line is exactly 79 characters
long, but I wanted to make it correct, not "cute".
I'll send this to the cypherspace people too, so they can correct
their web page.
--
Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
Dept. of Computer Sciences | "The box said 'Requires Windows 95, NT,
University of North Texas | or better,' so I installed Linux."
Denton, TX 76201 |
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: An extremely difficult (possibly original) cryptogram
Date: Thu, 29 Mar 2001 23:05:46 +0000
daniel mcgrath wrote:
> Jim, Doug -- how are you doing?
I've moved on again. See, for example, the challenge cryptogram at:
http://www.theregister.co.uk/content/28/17882.html
The prize is Sarah Flannery's book... or you could enter for the
Register "Show us the Money" t-shirt and a free entry to Bletchley
Park. :)
--
Jim Gillogly
Highday, 7 Astron S.R. 2001, 23:03
12.19.8.1.13, 7 Ben 16 Cumku, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Idea - (LONG)
Date: 29 Mar 2001 23:00:52 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
John A. Malley wrote:
>We tend to forget that perfect secrecy without an OTP is possible for a
>finite number of messages as illustrated by the example provided in the
>post.
Obviously it's possible to do this without an OTP, but as far as I
can tell, the resulting systems are no more practical than a OTP is,
so what's the point?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: DES key replacement.
Date: Fri, 30 Mar 2001 01:09:59 +0200
Sam Simpson wrote:
>
> Is this hard to follow ;) <- Note the smiley again!
There are many smileys with different meanings. I am not
sure they have even standard meanings. That's why I tend
to miss them.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Steve Roberts)
Subject: Re: texts on factoring?
Date: Thu, 29 Mar 2001 23:14:04 GMT
"Sam Simpson" <[EMAIL PROTECTED]> wrote:
>Tom St Denis <[EMAIL PROTECTED]> wrote in message
>news:2LJw6.159996$[EMAIL PROTECTED]...
>
><SNIP>
>
>> > I think Koblitz is a good book, but is quite expensive.
>>
>> It's only 45$ at Amazon
>>
>http://www.amazon.com/exec/obidos/ASIN/0387942939/qid=985830984/sr=1-1/ref=s
>> c_b_2/102-5941110-7696927
>
>It's only 230 odd pages though!
>
>I wouldn't say it was bad value for money _if you need some of the content_,
>which you obviously do.
>
What the hell, mine cost me A$87 (probably about US$20 these days) but
I have had no end of pleasure from reading and owning it. Furthermore
Koblitz is handing over all his royalties to buy maths books for the
students of certain poor countries. I even felt ennobled by owning
his book. (And it scares people if you read it conspicuously at
meetings etc).
Steve
------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: AES - test vectors?
Date: 29 Mar 2001 23:29:57 GMT
Hi. I'm trying to get an AES implementation to work. However, I don't
understand the test vector format from the AES web page. The file
"ecb_e_m.txt" begins like this this:
I=0
KEY=00000000000000000000000000000000
PT=00000000000000000000000000000000
CT=C34C052CC0DA8D73451AFE5F03BE297F
I=1
KEY=C34C052CC0DA8D73451AFE5F03BE297F
PT=C34C052CC0DA8D73451AFE5F03BE297F
CT=0AC15A9AFBB24D54AD99E987208272E2
What does "I=0" mean?
What is a "Monte Carlo Test"?
When I encrypt PT=00000000000000000000000000000000 with
KEY=00000000000000000000000000000000 in 128/128 mode I get something
different than CT=C34C052CC0DA8D73451AFE5F03BE297F. Am I reading the
file wrong or is my implementation wrong?
Can anyone send me a binary snapshot of the BYTESUB 256byte lookup table?
I don't know if my implementation calculates it correctly or not.
Thank you in advance.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: TRNG question
Date: Thu, 29 Mar 2001 23:39:20 GMT
On Wed, 28 Mar 2001 04:18:46 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt Benjamin Goldberg
<[EMAIL PROTECTED]> wrote:
>A long while back, someone mentioned an RNG based on something called a
>metastable flipflop or somesuch. I looked it up, and found this page:
> http://www.imse.cnm.es/~barriga/absdigit.htm
E.g.:
Bellido, M., et. al. 1992. Simple Binary Random Number
Generator. Electronics Letters. 28(7): 617-618.
>The first three abstracts descibe what I'm looking for, but I can't find
>any online versions of the publications mentioned.
>
>From what I recall, the idea is to have two NOT gates,
also known as inverters
>wired so the
>output of each goes to the input of the other, and start with both
>inputs forced to an active state, and then release.
Figure 2 shows both the set and reset inputs coming from a clock.
There are thus *two* inputs to each inverter: the clock and also the
cross-coupling. One possible implication is that the clock enables
hidden Set / Reset transistors which force the latch one way or the
other.
The trick to make this work may be in sizing the latch inverter
transistors for low gain and low speed, and achieving exact balance in
the SR input transistors, which might even be used as resistors.
>The circuit rapidly
>changes back and forth between both-on and both-off [aka is in a
>metastable state],
No. The metastable state is a non-digital voltage level between logic
0 and logic 1. This is the voltage which, when placed at an input and
amplified through two inverting stages, produces that same voltage on
the second output. We know there must be such a point, because an
input which is "slightly 1" gives a hard 1 output, and "slightly 0"
gives a hard 0. Somewhere in between, some logic "unknown" voltage
must reproduce itself.
This situation is "stable" only in the peculiar sense that the input
voltage does not change, or perhaps is canceled by other changes. A
system in this state is poised to collapse in either direction as a
result of any voltage variation. Ideally, that would be some sort of
random noise on the input, but might also be power supply noise, which
might not be random but might produce an output could might seem
random.
In essence, the entire circuit is a way to use positive feedback to
produce a logic level from a tiny noise signal.
>until it eventually stops with one on and the other
>off. Which wire is on, and which is off, determines if the circuit
>outputs a one bit or a zero bit.
>
>Does anyone know of any other references to this kind of RNG, and does
>anyone have comments on whether this produces real, true, randomness?
Clearly the design is a sketch of an experimental CMOS chip with the
exact circuit design unstated. It is not likely to work with
conventional parts. They say (p. 617, col. 2):
". . . any asymmetry in the circuit or any slight change in the
starting state will perturb the flipflop ideal operation and preclude
its use as a random source.
"Beside internal dissymmetries in the flipflop (which can be reduced
by careful dimensioning and layout) there are dissymmetries caused by
deviations in the silicon process, by the wires connecting the system
to other subsystems in a chip and, mostly, by the charges stored in
the output and input nodes of the flopflop as a result of previous
transitions.
"Hence, it seems very difficult (if not impossible) to use a flipflop
as a practical random generator, although in theory it could perform
as such when operated in the vicinity of point M. [N.B. the
metastable level] However, we have done so, using some circuit
techniques, leading us to a generator whose behaviour is rather
similar to the an actual noise source."
The key phrase here may be: "using come circuit techniques," which
probably involves transistor sizing (thus setting the ON resistance
and speed) and that sort of thing. The actual techniques used are not
disclosed.
I have experimented with HC logic gates in several different circuits,
but have so far been unable to find one which performs in any useful
metastable manner. I suspect that normal logic gates will always have
too much gain, although ECL might be attractive.
There was some previous discussion of a PLL approach which drove the
phase of a clock into the metastable timing region of an
edge-triggered FF. I think that can be done, but it seems to imply
that the loop filter integrates past performance to produce the
current result, which has randomness implications. The approach is
also fairly complex, and I have not tried it.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Edmond Ho" <[EMAIL PROTECTED]>
Subject: Re: rc4
Date: Thu, 29 Mar 2001 15:42:28 -0800
thanks a lot, i'm getting the correct results now (with your corrected
code). i was actually wondering about that loop; it seemed really clever to
use instead of a for loop to initialize the state array.
ed
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Idea - (LONG)
Date: Fri, 30 Mar 2001 00:01:50 GMT
"SCOTT19U.ZIP_GUY" wrote:
> ... in the 40's Shannon felt long keys were needed.
That isn't quite what he said. He demonstrated that, based on
consideration of information content alone, *one way* to attain
(perfect) secrecy was to obscure the PT with a sufficient amount
entropy from a secret key. But that is usually impractical, so
methods were developed that take into account how much *work*
must be done to extract the hidden information in the presence
of the key entropy. As recently explored in another thread,
there is a difference between theoretical secrecy and practical
secrecy, and in the real world practical secrecy is all that we
actually need. How to attain that is the big question.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Breaking a DES encrypted code.
Date: Fri, 30 Mar 2001 00:06:48 GMT
William Hugh Murray wrote:
> Enigma was, and is still, a strong cipher. What was exploited in
> Ultra was poor use of the cipher.
Enigma is *not* a "strong" cipher, regardless of what method
Bletchley Park employed against it. There are several cryppies,
possibly mostly retired by now, who know how to mount much
better attacks against such simple rotor systems. Indeed, more
complicated rotor systems (e.g. Geheimschreiber) were broken by
analytical methods not relying on "poor use" of the system.
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
