Cryptography-Digest Digest #69, Volume #13 Wed, 1 Nov 00 15:13:00 EST
Contents:
Re: RSA Multiprime (Francois Grieu)
Re: frequency analysis (Richard Heathfield)
Re: Psuedo-random number generator (Mike Rosing)
Re: Is RSA provably secure under some conditions? (Roger Schlafly)
Re: Psuedo-random number generator ([EMAIL PROTECTED])
Re: Emacs hack for OpenSSL encryption ([EMAIL PROTECTED])
Re: Give it up? (Mok-Kong Shen)
Re: Give it up? (Mok-Kong Shen)
Re: frequency analysis (JPeschel)
Re: BENNY AND THE MTB? (SCOTT19U.ZIP_GUY)
Re: XOR based key exchange protocol - flawed? (David Wagner)
Re: XOR based key exchange protocol - flawed? (David Wagner)
Re: BENNY AND THE MTB? ([EMAIL PROTECTED])
RSA MGF ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: RSA Multiprime
Date: Wed, 01 Nov 2000 15:46:22 +0100
[EMAIL PROTECTED] (Tony L. Svanstrom) wrote:
> Bob Silverman wrote:
> > Because of the way our (US) laws work, one can't just go into court
> > and say "I challenge this patent".
> > One must VIOLATE the patent, then have the owner sue you over the
> > violation. It is a protracted and messy and expensive process.
> >
> Is it like that with all patents, that once the public finds out about
> them the are already set in stone and you need to get sued to be able
> to challenge it? I have a hard time believing that, it simply sounds
> too stupid to be true.
In Europe, a patent can be challenged even if the patentholder is not
willing to sue. It sometime happens, but the problem is: who wants to
bear the cost of challenging a patent if not using the technique
described and beeing asked money for it by the patentholder ?
So it often gets back to the US situation.
The cases of challenged patent tend to fall into one of five categories:
- the patentholder is engaged in the process of suing, and the
infringer prefers to attack than defend (most frequent)
- the challenger wants to know in advance if it will be necessary to
pay, and how much, to use a technique, and prefers the case settled
than live with an unforecasted cost
- the challenger wants to make money from an existing patent in the
same field
- the challenger thinks that for ethical reasons the technique
described should not be used, like a genetic manipulation technique;
so the challenger use the tactic of making the patentholder unable
to get cash by making impossible to license the patent, in order to
discourage other companies from doing the same kind of research.
- the challenger thinks that for ethical reasons the technique
described should be freely usable [use of a genome, which really
is the same example as above !].
Francois Grieu
------------------------------
Date: Wed, 01 Nov 2000 17:45:20 +0000
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: frequency analysis
JPeschel wrote:
>
> Richard Heathfield [EMAIL PROTECTED] writes, in part:
>
> >Okay, that's it. I'd appreciate the opinions of the clueful on whether
> >this is any use for elementary cryptanalysis, or whether it should be
> >relegated to rec.puzzles.
>
> Yes, I think it's useful, and it's a good
> start.
>
> The program, though, has problems displaying
> large files, or maybe I just haven't figured
> out to do it.
So just use small files! :-)
No, seriously, I had the same problem, so I addressed it. You can
display any subset you like, using start and end offsets.
cipher 10 80
will display the ciphertext starting at byte 10 (i.e. the 11th byte) and
continuing until byte 80 (the 81st byte).
This works for "plain" and "both" too.
> Here's what I mean. The display
> of a large ciphertext or plaintext file, or
> both files scrolls off the screen. I'd like
> to see the program pause, by default, after
> 20 or so lines. I tried /p and piping MORE,
> but those tries didn't work. Additionally,
> you might want to include an option to display
> specific ciphertext-plaintext lines.
I think it would be better, too, to interleave ciphertext and plaintext,
rather than having one after the other. Unfortunately, this involves
knowing how wide the screen is, which is non-portable knowledge. I guess
I could make it a runtime arg though...
>
> It might be good to make the program capable of
> re-directing things like FREQ, MATCH, and
> LOOKUP to a file.
Perhaps. I was of the opinion that, if it didn't fit on the screen, I
should go find a better pattern to search! But yes, point taken.
>
> *******************************************************
> I think one of the first things the program should
> try to determine is whether the cipher is
> monoalphabetic. As it is, the user could
> determine that from the single-character
> frequencies by looking for matching peaks
> and valleys. But you could have the program
> calculate the IC. Given enough ciphertext
> the IC is reliable at determining monoalphabeticity.
I wasn't planning to use the IC until Vigenere, but if it can be used to
determine monoalphabeticity (nice word - if it /is/ a word!), then it
would indeed be a useful addition.
>
> MATCH is a fairly good way to solve ciphers where
> word divisions are apparent. I would, though,
> like to be able to preserve the character
> substitutions I've already made, and, then
> be able to do a match.
Good point.
>
> A quick way to solve shift ciphers might be
> added.
Sorry - you'll need to explain that.
>
> I see you plan to use digraph, trigraph,
> and tetragraph analysis -- good idea.
Tetragraph is not firmed up yet - 26^4 is a big number - but I will
certainly be looking at it in a positive light.
>
> I'd try to keep the program interactive rather than
> make it a fire-and-forget program -- unless
> you are planning on writing a genetic or
> hillclimbing algorithm.
I know a cryptanalyst would prefer a batch process, and I'm tempted to
write one mainly because I'm not immediately sure how to go about it
(i.e. it'll be a learning process, which is always a good idea), but I
do like the interactive approach because it's fun to use.
>
> *******************************************************
>
> If your news server gets alt.sources.crypto,
> you might want to post your code there, too.
> It would be nice to make that news group
> more popular, or at least keep it alive.
Thanks for the tip. :-)
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Psuedo-random number generator
Date: Wed, 01 Nov 2000 11:47:52 -0600
Terry Ritter wrote:
> Thank you. You are of course aware that I maintain a literature
> survey on physically random generators:
>
> http://www.io.com/~ritter/RES/RNGMACH.HTM
>
> If you have any others, I would love to see them too.
Terry, you can add this one to your list:
http://www.terracom.net/~eresrch/detecting_random.ps
This is based on many of those articles already in the list. The
advantage is that there is no dead time for the detector. The
academics didn't consider it significant, but I think the basic
concept is useful for many other sources of RNG. (The paper
was "accepted if there's room for it" to the first CHES conference,
but there wasn't room :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Wed, 01 Nov 2000 10:02:35 -0800
Shai Halevi wrote:
> In the mean time, my personal interpretation of proofs of security in
> the random oracle model is that such system is secure, unless:
> (a) the underlying assumption (e.g. factoring) is wrong,
> (b) there is a flaw in the specific hash function that is used, or
> (c) someone finds an attack that uses the hash function code in any way
> other than just running it.
I guess I agree with this, but I still think that they ought to called
heuristics and not proofs of security because of the ambiguity in
those conditions.
In particular, what is a hash function flaw? SHA-1 was designed to
be collision resistant. If it turned out that the first bit of the
output of SHA-1 is zero 51% of the time, that info would have no
effect on the intended purpose of SHA-1. But it might totally
destroy some random oracle usage of SHA-1.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Psuedo-random number generator
Date: Wed, 01 Nov 2000 17:58:56 GMT
How about some decimal dice, like in Dungeons - & - Dragons?
Go to your local gamer's store and they will have them by the dozen.
Very low-tech, very effective. I recommend getting 5 in different
colours and throwing them all at once, having first decided on an order
for the colours.
>
--
| || \ __/__ / \ _/_ | || /
| _|_ ,--, / \ /_ | -+- / ,-. | /
| V T_) | | | \ | | | / _
\_/ + / `' ' __/ \ / `-' \_/ L/ \
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Emacs hack for OpenSSL encryption
Date: Wed, 01 Nov 2000 18:31:20 GMT
David Rush <[EMAIL PROTECTED]> wrote:
> I find it dismaying how little free (speech) software exists for
> securing files (as opposed to email). Here's my US$0.02. I'm hoping
> that someone finds it useful.
To be fair, most of those "email" packages can also work on files
painlessly. (ie, pgp or gpg with the -c option) As to the rest, I
suspect most people find encryption at the file system level more
convient. (ie, scramdisk, encrypted loopback mounts, CFS, etc)
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Date: Wed, 01 Nov 2000 19:44:06 +0100
Tom St Denis wrote:
>
> Um it's rather obvious what my point is. "Security != codec". i.e, get
> your security from ciphers and cryptography and not from a huffman
> codec.
>
> If you can't comprehend this... well too bad.
Ah, but you unfortunatedly chose to use a shorthand
'codec' which I have never seen before and which I doubt
is in commen usage. If you intend to claim that 1-1
compression is not relevant to security, then you should
express yourself in a bit more detail and not let others
to 'solve puzzles'. It is better that you join the threads
that discuss that. There is currently one, if I don't err.
You may indeed have a good chance of establishing your
arguments. A couple of times I tried to discuss that
myself with proponent of 1-1 but I found that, because of
certain difference in opinion on style of debate, it was
rather difficult for me to proceed very far. Maybe I
would try someday once again, but I don't know.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Give it up?
Date: Wed, 01 Nov 2000 19:47:09 +0100
Tom St Denis wrote:
>
> Pascal JUNOD <[EMAIL PROTECTED]> wrote:
> > > This is sci.crypt not "sci.post.whatever.you.want.crypt"
> >
> > That's funny to read this from you...
> >
> > A+
>
> Hey joker, most of my posts are on topic (my ciphers I propose, my
> analysis of some others, etc...) you guys just don't respond to my
> positive posts at all.
I answered in another recent thread to a post of yours,
giving a number of reasons why an article can fail to get
follow-ups.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: frequency analysis
Date: 01 Nov 2000 19:12:03 GMT
Richard Heathfield [EMAIL PROTECTED] writes, in part:
>JPeschel wrote:
>>
>> Richard Heathfield [EMAIL PROTECTED] writes, in part:
>>
>> >Okay, that's it. I'd appreciate the opinions of the clueful on whether
>> >this is any use for elementary cryptanalysis, or whether it should be
>> >relegated to rec.puzzles.
>>
>> Yes, I think it's useful, and it's a good
>> start.
>>
>> The program, though, has problems displaying
>> large files, or maybe I just haven't figured
>> out to do it.
>
>So just use small files! :-)
Ha! Sounds like something I would've said. :-)
>
>No, seriously, I had the same problem, so I addressed it. You can
>display any subset you like, using start and end offsets.
>
>cipher 10 80
>
>will display the ciphertext starting at byte 10 (i.e. the 11th byte) and
>continuing until byte 80 (the 81st byte).
>
>This works for "plain" and "both" too.
Thanks.
>> *******************************************************
>> I think one of the first things the program should
>> try to determine is whether the cipher is
>> monoalphabetic. As it is, the user could
>> determine that from the single-character
>> frequencies by looking for matching peaks
>> and valleys. But you could have the program
>> calculate the IC. Given enough ciphertext
>> the IC is reliable at determining monoalphabeticity.
>
>I wasn't planning to use the IC until Vigenere, but if it can be used to
>determine monoalphabeticity (nice word - if it /is/ a word!), then it
>would indeed be a useful addition.
Yes, monoalphabeticity is a word: Friedman used it in Mil. Crypt.
Probably tough to find it in an ordinary dictionary, though.
When you use the IC to determine the length of Vigenere key
you're running a calculation over individual alphabets. Let's
pretend the monoalphabetic cipher is a Vigenere with a period
of 1. The calculated IC, given enough ciphertext, should be about
that of normal English, about .67. The ciphertext and plaintext
of a monoalphabetic cipher have exactly the same IC.
>> A quick way to solve shift ciphers might be
>> added.
>
>Sorry - you'll need to explain that.
A shift cipher is a monoalphabetic substitution cipher that uses
a direct standard alphabet. You shift the characters a certain
number of places. For instance, the Caesar cipher shifts by 3 places.
In a 26 character alphabet there are only 25 possible shifts, other
than the original plaintext. So you could just display numbered
lines of 25 possible shifts, let the user pick the line that looks
reasonable, and write the decrypted file.
>
>>
>> I see you plan to use digraph, trigraph,
>> and tetragraph analysis -- good idea.
>
>Tetragraph is not firmed up yet - 26^4 is a big number - but I will
>certainly be looking at it in a positive light.
Don't do it that way! Use the top 20 or so digraphs, trigraphs,
and tetragraphs, and maybe a few of the least used, too.
>> If your news server gets alt.sources.crypto,
>> you might want to post your code there, too.
>> It would be nice to make that news group
>> more popular, or at least keep it alive.
>
>Thanks for the tip. :-)
>
Welcome.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: BENNY AND THE MTB?
Date: 1 Nov 2000 19:22:07 GMT
[EMAIL PROTECTED] (Richard Heathfield) wrote in
<[EMAIL PROTECTED]>:
>Tim Tyler wrote:
>>
><snip>
>>
>> Not so. Could it be that you are aauming that a 8 bit cyphertext need
>> map to an 8 bit plaintext? It need not - and indeed in Matt's code,
>> it typically does not - an 8-bit byte cyphertext typically maps to a
>> much longer plaintext.
>
>I can see how the 8-bit ciphertext could effectively be the equivalent
>of a code-book header entry, and that the plaintext would be in the body
>of that entry. But I don't think that's what you mean, so I'm baffled.
>
>>
>> I don't think "256 messages" comes into it. The interceptors have
>> received a *particular* byte. They are not considering what messages
>> could be transmitted by *any* single byte value, but the message that
>> is *actually* transmitted by one specific byte - the one they have
>> intercepted.
>
>If this is only one byte out of many, then I withdraw my bafflement -
>it's just a partial ciphertext, and that puts a completely different
>complexion on things.
It might be better to wait for Tims words if mine inflame you.
But I can;t resest the temptaion to try. But in the example the
ciphertext which just happened to be "8 bits" for the compressed
encrypted message. For the key I used the actaul message was 19
bytes ( words) So ever got it would have to go to the code dictionary
to find the actually message whicj would contain 19 words.
>
>>
>> There are probably almost as many possible messages that could be
>> represented by that single bye as there are keys; since almost every
>> key is likely to lead to a different message.
>
>Okay, my layman's reasoning is that there are 2^128 keys and 2^8
>ciphertexts, so there are a total of 2^136 possible messages. If we are
>dealing with a specific key, however, then I can only see 256, no matter
>how long the key is.
>
>Perhaps my source of confusion is a relativistic one.
>
>From Bob's point of view, the incoming byte can only convey one of 256
>messages (if it is indeed a complete ciphertext - obviously, if it's a
>partial ciphertext, this doesn't apply).
No both know that the byte can only contain one of 256 possible
patterns. But I think what your missing is that the bijective compression
and encryption can not add information to the data it is working on.
Many methods like PGP do things so one can check to see if the correct
key is used. That does not happen in this kind of compression encryption.
NOTHING IS ADDED. But it may seem like a paradox that since the byte
can only be one of 256 message then the attacker in your mind ought to
be able to limit it down to 256 possible message. The key though
is that the attacker has no idea what key was used this key has many bits
long. Almost any key used will give a new possible message.
But what is true. Is that if the attacker knows what key was used.
He could consturct in advance what the possible message are. And for
a given key there are only 256 possible messages for one byte.
However if the attacker knows the key he might as well wait for
the message. Since it is most likely the most common messages will
be several bytes long.
I know this seems strange since it shows an extreme example. An
attacker can have several thousands of messages all of which could
have come from a single byte. But unless he has the Rijndael key he
is out of luck. Even if Rijndael is easy to break with quatum computers
if implemented poorly from an information point of view, As is the
standard practice in PGP.
>
>From Eve's perspective, however, I can easily see that there are 2^136
>/potential/ messages within that byte - but, again, only if it's part of
>a longer ciphertext.
It usually gets expanded to something larger than a single byte
when you decrypt and decompress.
but the byte is that total compressed and encrypted file.
It seems strange only because people have been expertly
psychologically conditioned to do compression and encryption
the wrong way so that groups like the NSA remain in control
and can break and read your code. I don't think Im smarter
than every one else. Many its the way my brain operates that
has given me partial immunity to this expert conditioning.
That has so much seemed to have inflected havic on the
open crypto community. It is so good that the misinformation
spreads just like a cult religon. Look at Tommy and the crap
he spreads I think he actually means well but he has this
software brain virus in a bad way I think.
>
>If it's on its own, there are only 256 different states which it can
>have. This is my stumbling block, I'm sure of it. You seem to be saying
>that you can encode > 256 states within an 8-bit byte, and I'm just not
>seeing it. Should I give up and go home?
>
>
NO NEVER GIVE UP TILL YOUR LAST BREATH!!!
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: XOR based key exchange protocol - flawed?
Date: 1 Nov 2000 19:29:22 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Mike Connell wrote:
>> [EMAIL PROTECTED] (David Wagner) writes:
>> > If you use RSA encryption, so that (Xa)Pb = Xa^Eb mod Nb (Pb = (Nb,Eb)),
>> > then an active attacker M can break the scheme by replacing the
>> > transmitted values (Xa)Pb with 0:
>> > a -> b : Pa
>> > a <- b : Pb
>> > a -> m : (Xa)Pb
>> > m -> b : 0
>> > m <- b : (Xb)Pa
>> > a <- m : 0
>> > Then M can predict the session key used, since 0^Db mod Nb = 0, etc.
>
>On further thinking, I'm not sure that I see the problem. In this
>case, after all the communication has taken place, the three entities
>are in this following positions:
>
> A has : Pa Pb Xa 0, computes Pa+Pb+Xa+0 = Pa+Pb+Xa
> B has : Pa Pb Xb 0, computes Pa+Pb+Xb+0 = Pa+Pb+Xb
Quite right. The so-called "attack" is bogus, and there is nothing
to worry about here. I was mistaken. Thanks for catching my error!
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: XOR based key exchange protocol - flawed?
Date: 1 Nov 2000 19:31:05 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Dan Oetting wrote:
>1. a -> b : Pa,(Xa)Pa
> a <- b : Pb,(Xb)Pb
>
>2. a -> b : (Xa)Pb
> a <- b : (Xb)Pa
>
>In the first step A and B exchange which keys to use and proof of the
>seeds to be exchanged. In the second step the seeds are exchanged.
In your first step, (Xa)Pa is just a commitment to Xa, which is opened
in the second step. However, using public key encryption for bit commitment
is pretty slow, and there are much faster schemes. See, e.g., Schneier's
_Applied Cryptography_ for several schemes using fast hash functions.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: BENNY AND THE MTB?
Date: Wed, 01 Nov 2000 19:35:35 GMT
Let's go back to mathematics again.
Assumptions:
Rijndael is a 128-bit block cipher
Rijndael diffuses data perfectly (this assumption is obviously not
true, but close enough to reality to make it functionally
indistinguishable)
Each triple T of (Plaintext, Ciphertext, Key) is unique in Rijndael
given the pair (Ciphertext, Key) the triple (Plaintext, Ciphertext,
Key)is uniquely computable
given the pair (Plaintext, Key) the triple (Plaintext, Ciphertext,
Key)is uniquely computable
Given a block of triple T of (Plaintext, Ciphertext, Key), where the
Plaintext is 128-bits, Ciphertext is 128-bits, and Key is as appropriate
Given Plaintext is Random (more specifically each possible plaintext is
equally likely).
Take the pair (Ciphertext, Key), this represents the triple T
Eliminate 1 bit of Ciphertext (with known placement), leaving only 127
known
bits
This identifies 2 values for plaintext, which by the random assumption
cannot be distinguished
Inaddition without computing the two values for the plaintext it is
impossible to know their relation (by the perfect diffusion assumption)
Extending this to the claimed limit we have:
Take the pair (Ciphertext, Key), this represents the triple T
Eliminate 120 bits of Ciphertext, leaving only 8 known bits
This identifies 2^120 values for plaintext, which by the random
assumption
cannot be distinguished
I'm sorry, but you have now given enough information to PROVE that Matt
is not using Rijndael, he is using some homegrown cipher that he has
chosen to name Rijndael.
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: RSA MGF
Date: Wed, 01 Nov 2000 19:38:01 GMT
In RFC 2437, a Mask Generation Function is defined for use as encoding
algorithm. Part of the algorithm is:
For count from 0 to \lceil{l / hLen}\rceil-1 ...
I do not understand the second part of this. What is "lceil"
and "rceil"?
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
