Cryptography-Digest Digest #294, Volume #10 Wed, 22 Sep 99 11:13:05 EDT
Contents:
Re: Yarrow: a problem -- am I imagining it? ("Richard Parker")
Re: Yarrow: a problem -- am I imagining it? ("Richard Parker")
Re: crypto papers (Helger Lipmaa)
Re: RSA 640 bits keys factored, French banking smart card system craked! (Thomas
Pornin)
Re: crypto papers (Tom St Denis)
msg for Dave Scott (Tom St Denis)
Re: Okay "experts," how do you do it?
Re: Comments on ECC (Bob Silverman)
Re: Galois field isomorphism? (Bob Silverman)
Re: RSA 640 bits keys factored, French banking smart card system craked! (Mok-Kong
Shen)
Re: msg for Dave Scott ("Anonymous")
Modified CBC ("Adam Pridmore")
Re: frequency of prime numbers? (David Hoyt)
Purdue's Large Number (John M. Gamble)
Re: Modified CBC (Jim Gillogly)
Re: arguement against randomness (Tim Tyler)
----------------------------------------------------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: Wed, 22 Sep 1999 08:00:59 GMT
Eric Lee Green <[EMAIL PROTECTED]> wrote:
> Richard Parker wrote:
>> Given your design goals, I think the following PRNG construction is
>> both simpler and has superior resistance to attack:
>>
>> k_0 = H(initial entropy)
>> R_i = E(k_{i-1}, 2i-1)
>> k_i = E(k_{i-1}, 2i)
>
> Hmm, it appears that you're using half of the output of the block cipher
> to re-key itself, and the other half as values. I'm not sure how that's
> going to be more secure than just using the output of the block cipher
> directly. Well, yes, I see, it will make predictive attacks quite
> difficult. Hmm. Interesting. On the other hand, will the output develop
> a pattern, given that you're basically feeding a function its own
> output? Many functions will swiftly converge if fed their own output
> (hmm, is that called negative feedback? It's been 17 years since I took
> EE101, so forgive me if I forget). Other functions will diverge and
> start jumping all over the place if fed their own output, but may jump
> in predictable ways. It seems to me you're betting on some
> characteristics of E() that may or may not be justified. Whereas we know
> that if E() is a strong cipher, its output in counter mode cannot be
> predicted unless you have the key (or unless you exhaust the key space
> of the block counter before you re-key the beast, but that's not very
> probable with a 128-bit block cipher!).
>
> In short: your construction has superior resistance to attack only if
> you make the assumption that its output will not converge in a known
> fashion when its output is fed back into itself as part of a feedback
> loop. Do you have any rationale for making such an assumption?
Well, assume an attacker knows the counter but does not know the
original key. Further assume that this attacker can successfully
predict the next PRNG value by exploiting the fact that the block
cipher is used to rekey itself. Such an attacker can also mount a
successful related key attack on the block cipher by noting that the
derived keys K' are related to the original unknown key K by the
relation K' = E(K). So, if the block cipher is resistant to related
key attacks then this PRNG should be secure.
While I don't think such a strong security assumption is necessary for
the output to not converge, I confess that a proof based on a lesser
security assumption doesn't immediately come to my mind.
-Richard
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: Yarrow: a problem -- am I imagining it?
Date: Wed, 22 Sep 1999 10:03:09 GMT
"Richard Parker" <[EMAIL PROTECTED]> wrote:
> So, if the block cipher is resistant to related key attacks then this PRNG
> should be secure.
>
> While I don't think such a strong security assumption is necessary for
> the output to not converge, I confess that a proof based on a lesser
> security assumption doesn't immediately come to my mind.
I think I have an argument that uses a weaker assumption than my first
argument, however, the result is weaker as well. While the first
argument showed that rekeying the block cipher does not cause a
predictable PRNG output, this argument only shows that the PRNG will
not converge.
Assume that the block cipher used in the PRNG is a random function of
its key and a plaintext block. The new key is created as a function
of both the old key and a counter, and because the counter increments
the new key will not directly cycle. Therefore by the birthday
paradox the PRNG will generate about 2^(k/2) n-bit blocks of output
before it becomes likely that the same key will be used twice.
-Richard
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: crypto papers
Date: Wed, 22 Sep 1999 14:02:28 +0300
David A Molnar wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > The only reason I offer this is because when I started in crypto I found it
> > really tedius to find anything worth reading... the list of papers is about 6
> > months of work or so...
>
> Maybe an annotated bibliography would be good, then ? You can put up the
> list, plus some notes on "I liked this paper," or "Not very clear why this
> was written," or whatever. It'll take 10K max. Then at the bottom note
> that you are willing to e-mail papers out.
Take some link from http://home.cyber.ee/helger/crypto/link/biblio.html, as an
example.
Helger
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Crossposted-To: alt.security.pgp
Subject: Re: RSA 640 bits keys factored, French banking smart card system craked!
Date: 22 Sep 1999 11:13:39 GMT
According to Paul Rubin <[EMAIL PROTECTED]>:
> Anyway, this is an interesting security story, but without more
> details, it's not a cryptography story. I consider it fishy that
> Humpich won't be more specific about what he did.
Humpich is not a cryptographer. It is quite possible that the RSA modulus
was only 320 bits long, and that the 640 bits thing is the sum of the
modulus and the public exponent. This would be coherent with other
informations about the protocols used in theses cards (signed with a
320-bit RSA -- which is weak, but the public modulus was supposed to
remain secret, inside tamper-resistant devices; Humpich did at least
a good job of reverse-engineering).
--Thomas Pornin
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: crypto papers
Date: Wed, 22 Sep 1999 12:05:50 GMT
In article <7s94tb$edv$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > The only reason I offer this is because when I started in crypto I found it
> > really tedius to find anything worth reading... the list of papers is about 6
> > months of work or so...
>
> Maybe an annotated bibliography would be good, then ? You can put up the
> list, plus some notes on "I liked this paper," or "Not very clear why this
> was written," or whatever. It'll take 10K max. Then at the bottom note
> that you are willing to e-mail papers out.
>
Well I will talk with Stephen Alexander (the cool dude hosting peekboo for
me) and see if I can upload all the papers. Then I can simply make a pretty
website like some other user commented about.
My comments would go as far as 'good introduction' or 'very detailed' since I
am rather busy with Peekboo now... :)
Thanks for the ideas though :)
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: msg for Dave Scott
Date: Wed, 22 Sep 1999 12:09:57 GMT
Well you say you can break all encryption methods and systems. Prove it.
beaqaaamL6MNs6}utuaaaaiaaaaW{dsG{jC4KzE3hoqb}tWYZ9qT2Fcaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaa
That was a peekboo message using my private key and csybrandy's public key.
It was encrypted with RC4. I want to see if you can read the message, get
the private key or both. The source and executables are all up on
http://www.cell2000.net/security/peekboo/index.html
And if you can't break peekboo, then I think you shut up, cuz I am just a
kid, and if I could make peekboo imagine what wonder Comp sci majors and
crypto 'gods' could do....
(btw if anyone else reads this thread and thinks I am a jerk now can you do
something usefull and makesure that the dh generator is actually a proper
one. I was told by some people in this group it's ok....)
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Okay "experts," how do you do it?
Date: 22 Sep 99 12:13:50 GMT
Sundial Services ([EMAIL PROTECTED]) wrote:
: Ahh yes, the NP-complete problem.
: Okay, then, "for-GET how it works." Let's look only at the input, the
: output, and the key. Let's pretend we cannot determine the algorithm.
: What is it about an algorithm's input and output that enables us to say
: that it is a "good" encryption algorithm? What is it about the
: algorithm's dependence upon its two inputs, 'p' and 'k', as realized in
: the output 'c', that makes the algorithm a "good" one or a "bad" one?
Well, c shouldn't correlate to either p or k in a simple way.
The trouble is, of course, that an algorithm may be weak against
cryptanalysis even if the "simple" relationship between c and p and k is
still much too hard to detect either by any automated analysis of the
algorithm, or by a combined automated and manual analysis of the cipher's
inputs and outputs, treating it as a black box.
Bringing human ingenuity to bear on the description of the algorithm is a
stronger attack, and thus a cipher can be invincible against a black-box
attack without that being very useful, because that attack is very much
weaker.
John Savard
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Comments on ECC
Date: Wed, 22 Sep 1999 11:38:30 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jerry Coffin) wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
> > All crypto algorithms I know are in NP, if only for the reason that using the
> > private key must take a reasonable amount of time. So a trivial NP solution to
> > solving the ECDLP or DLP is guess the correct private key.
>
> I'm assuming you meant to use "P" where you said "NP" above
> (otherwise, I can't decipher your statement into anything meaningful).
He said NP, he meant NP, and NP is correct.
I suggest you study this subject before you say anything further.
>
> Keep in mind that "NP" means "modernistic polynomial."
^^^^^^^^
WHAT??????
> IOW, even
> assuming that there really is such a thing as an NP-complete problem
> (I.e. that P!=NP)
Now you are sounding like a total crank who does not know what
he is talking about. Of course NP-Complete problems exist
and their existence does NOT imply P != NP.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Galois field isomorphism?
Date: Wed, 22 Sep 1999 11:48:11 GMT
In article <[EMAIL PROTECTED]>,
Paul Crowley <[EMAIL PROTECTED]> wrote:
> I'm told that there's really only one GF(2^8), and that all the
> irreducible polynomials you can use as bases just give you different
> ways of representing it.
Correct. Two finite fields are isomorphic iff they have the same
number of elements.
>
> How do I convert between different representations, given their basis
> polynomials?
It's simple linear algebra.
See IEEE P1363 for examples, or consult any textbook on
abstract algebra.
See also, Lidl & Neidereiter "Finite Fields". This is *the* work
on the subject.
> Are there non-trivial isomorphisms from the set onto
> itself?
Yes. The Frobenius map is one such.
It seems as if it must be a linear mapping by definition,
> since addition is the same in any representation and
> f(a) + f(b) = f(a + b) ; is that right?
Essentally, yes.
>
> What's the best textbook for this sort of thing?
See above
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: RSA 640 bits keys factored, French banking smart card system craked!
Date: Wed, 22 Sep 1999 14:52:43 +0200
Paul Rubin wrote:
>
> Anyway, this is an interesting security story, but without more
> details, it's not a cryptography story. I consider it fishy that
> Humpich won't be more specific about what he did.
I am not very sure whether you would have behaved entirely differently
if you were at his place. I mean you would have been in a different
psychological and reasoning state. From the meager material present
on the web page it seems plausible to deduce that they (undefined)
are much more interested in securing his method of factoring than
in deteriming the very act of forgery (which he has voluntarily
admitted in the first place anyway) and hence applying law enforcement.
It may be of interest to note that sometime ago in this group
someone asked whether it could be dangerous to his life if he
succeeded and announced the factoring of a very huge number.
(Whereupon I replied that I would venture to do the announcement
for him in my name, though I see some difficulty of handing over
the prize which is paid out to me to him.)
M. K. Shen
------------------------------
From: "Anonymous" <[EMAIL PROTECTED]>
Subject: Re: msg for Dave Scott
Date: Wed, 22 Sep 1999 09:29:03 -0400
Really???? Why all the repeated characters if it *is* RC4??
Tom St Denis wrote in message <7sagud$4ad$[EMAIL PROTECTED]>...
>Well you say you can break all encryption methods and systems. Prove it.
>
>beaqaaamL6MNs6}utuaaaaiaaaaW{dsG{jC4KzE3hoqb}tWYZ9qT2Fcaaaaaaaaaaaaa
>aaaaaaaaaaaaaaaaaaaaaaaaa
>
>That was a peekboo message using my private key and csybrandy's public key.
>It was encrypted with RC4. I want to see if you can read the message, get
>the private key or both. The source and executables are all up on
>
>http://www.cell2000.net/security/peekboo/index.html
>
>And if you can't break peekboo, then I think you shut up, cuz I am just a
>kid, and if I could make peekboo imagine what wonder Comp sci majors and
>crypto 'gods' could do....
>
>(btw if anyone else reads this thread and thinks I am a jerk now can you do
>something usefull and makesure that the dh generator is actually a proper
>one. I was told by some people in this group it's ok....)
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Share what you know. Learn what you don't.
------------------------------
From: "Adam Pridmore" <[EMAIL PROTECTED]>
Subject: Modified CBC
Date: Wed, 22 Sep 1999 14:31:53 +0100
I am interested in using a very simple block cipher mode on a symmetric
algorithm to prevent blocks from being swapped, or replaced.
I wanted to know if there would be any security loss in using a simpler
version of CBC.
The version I wished to use is to encrypt the first block with the Key (no
IV), Then each subsequent block is XOR'ed with the previous cipher text
block and then encrypted with the key.
Thus the cipher text will be the same size as the original plaintext.
(ignoring padding issues!)
No to messages will be encrypted with the same key.
The difference between this and CBC is the IV is dropped, and no two
messages will be encrypted with the same key.
I can't see any problems with this. Opinions?
Cheers Adam
------------------------------
From: David Hoyt <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Wed, 22 Sep 1999 08:59:08 -0500
Actually, Godel said ANY axiomatic language is EITHER incomplete
OR inconsistent. Logic and math are axiomatic languages. Most
of us hope that they are incomplete (some things are not
provable), but it is possible that they are inconsistent.
Until someone can prove the TRUE == FALSE, we won't know.
Also, if "axiom set X" can prove Y, and math/logic can't,
then at best math/logic can be used to validate the internal
consistency of the particular proof X->Y. It can't be used
to refute Y. Thus a scientist can believe in christian (or
ojibwe) creationism, and evolution at the same time.
Most of us (in this group at least), use the word provable
to mean within the axiomatic languages of math/logic. Certainly
any crypto system will be analyzed with this language. Any other
language will be even further off topic than this is.
david | [EMAIL PROTECTED]
Tim Tyler wrote:
> Donald Welsh <[EMAIL PROTECTED]> wrote:
> : On Fri, 06 Aug 1999 17:27:45 GMT, Bob Silverman <[EMAIL PROTECTED]> wrote:
>
> :>No. What Goedel showed was that any sufficiently rich axiomatic
> :>system is incomplete in the sense that there are true statements
> :>which can not be proved. [...]
>
> : I'd like to correct this misconception, if I may. Godel's theorem
> : does not say that "there are true statements that cannot be proved".
> : It says that there are unprovable statements. These statements are
> : neither true nor false.
>
> Such statements are neither true nor false *from within the axiom system
> in question*.
>
> Calling it a misconception may be a bit strong: Godel demonstrated
> sentences which read like "axiom set X can never prove this statement to
> be true", which an external observer not bound by axiom set X genuinely
> *could* verify as being true statements.
------------------------------
From: [EMAIL PROTECTED] (John M. Gamble)
Crossposted-To: sci.math
Subject: Purdue's Large Number
Date: 22 Sep 1999 13:48:50 GMT
First, a quote from the Chicago Sun-Times's Quick-Takes
column, May 7 1997:
"Purdue University cryptographers are looking for help in factoring a
number.
"That is, they are searching for two numbers that, multiplied together,
result in the number they are studying.
"Seven and five are factors of 35, for example.
"The number Purdue needs to factor is
163790195580536623921741301545704495839
239656848327040249837817092396946863513
212041565096492260805419718247075557971
445689690738777729730388837174490306288
87379284041.
"You will probably need your pocket calculator for this."
The hexadecimal representation of this number, by the way, is
11c6d37d2dd907c2b563c229d9c74a6caad0d3723f0777622b6b979252be3c5e
734c7fdc9e974e2e6dfcc748525918ef21b79a6e3bb6c7dc12a481d0bce1f4c3
b92af9f9049, a value provided with help from the perl BigInt package.
Anyone know why this particular number? Anyone know of its
status as far as factoring goes?
Thanks,
-john
February 28 1997: Last day libraries could order catalogue cards
from the Library of Congress.
--
Pursuant to US Code, Title 47, Chapter 5, Subchapter II, '227,
any and all unsolicited commercial E-mail sent to this address
is subject to a download and archival fee in the amount of $500
US. E-mailing denotes acceptance of these terms.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Modified CBC
Date: Wed, 22 Sep 1999 14:16:36 +0000
Adam Pridmore wrote:
> I wanted to know if there would be any security loss in using a simpler
> version of CBC.
>
> The version I wished to use is to encrypt the first block with the Key (no
> IV), Then each subsequent block is XOR'ed with the previous cipher text
> block and then encrypted with the key.
>
> Thus the cipher text will be the same size as the original plaintext.
> (ignoring padding issues!)
...
> The difference between this and CBC is the IV is dropped, and no two
> messages will be encrypted with the same key.
>
> I can't see any problems with this. Opinions?
Depends on what you want to use it for, but it needs a lot more keying
material than CBC, which extends key life by using the IV. You still
have to pass the key to your recipient, which will presumably be as long
as or longer than the IV if you were doing CBC, and you have to do it
securely, unlike the CBC case where you leave the IV in the opening.
So although the ct is the same size as the pt, you're passing at least
as much data as the CBC, and this time you have to pass the extra stuff
securely. Doesn't look like a win in the general case, but you may have
a specialized app where it will be helpful.
--
Jim Gillogly
Sterday, 1 Winterfilth S.R. 1999, 14:11
12.19.6.9.19, 12 Cauac 7 Chen, First Lord of Night
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: arguement against randomness
Reply-To: [EMAIL PROTECTED]
Date: Wed, 22 Sep 1999 14:04:55 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> I thought atomic clocks depended on vibrations in crystalline lattices
:> rather than radioactive decay.
: No. Those are "crystal" oscillators.
Right...
So *where* is "the randomness of radioactive decay being used to drive the
most accurate clocks we've invented..."?
AFAIK, the only occasion radioactivity is explicitly used in estimating
time periods is when using techniques like carbon-dating.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Real love stories have no ending.
------------------------------
** 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
******************************
