Cryptography-Digest Digest #456, Volume #13 Thu, 11 Jan 01 16:13:01 EST
Contents:
Re: Stream cipher ("John A. Malley")
Re: RSA recoverable signature trick (Mark Currie)
Re: RSA recoverable signature trick (Mark Currie)
Re: DES validation ([EMAIL PROTECTED])
Re: NSA and Linux Security ("Douglas A. Gwyn")
Re: Comparison of ECDLP vs. DLP (David Wagner)
Re: Comparison of ECDLP vs. DLP (Roger Schlafly)
Re: Comparison of ECDLP vs. DLP (William Hugh Murray)
Re: keeping secret keys secret (William Hugh Murray)
Re: NSA and Linux Security (William Hugh Murray)
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution (William Hugh
Murray)
Re: Comparison of ECDLP vs. DLP (DJohn37050)
Re: NSA and Linux Security ([EMAIL PROTECTED])
Re: NSA and Linux Security (Mok-Kong Shen)
Re: Comparison of ECDLP vs. DLP (David Wagner)
Re: Comparison of ECDLP vs. DLP (David Wagner)
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Stream cipher
Date: Thu, 11 Jan 2001 07:14:41 -0800
David Wagner wrote:
>
> This is an xor of six Vigenere's, each with period about 2^16.
> Thus, with 6 * 2^16 bits of known plaintext, you can break it.
>
> You don't even need to know how each of the six generators work
> (you could replace them with any other scheme with similar period,
> and the attack would still work).
I can see this attack working if the XORed output of the six
congruential generators is the "running-key" for a simple XOR cipher
with the plaintext. With known plaintext one gets the running-key
stream and much information about the states of the generators.
Mr. Johnson's running-key generator uses only the LSB of the six XORed
LCG outputs as its output to hide the state of the generator.
Does the reduction of the XORed output of the six generators just make
the suggested attack more difficult but still possible?
John A. Malley
[EMAIL PROTECTED]
------------------------------
Subject: Re: RSA recoverable signature trick
From: [EMAIL PROTECTED] (Mark Currie)
Date: 11 Jan 2001 16:04:02 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>Mark Currie wrote:
>>
>> Thank you, I actually remember discovering this problem way back while
>> questioning the need for the large padding string in the PKCS signature
format.
>> I definately will not use this method. However it may still be useful to
find a
>> neat way around the equal modulii thing in the case where you may want to
>> encrypt a signature. Can you think of any problems associated with this
>> variation ?
>
>That depends on the signature. If the man-in-the attacker is able to
>replace the public key used by the recipient to verify the signature,
>you still have the same problem. It really depends on the exact details
>of the protocol, and this seems to me to be a weakness.
>
>In cryptography I would always stick with the standard methods. If you
>try to invent something on your own, chances are it has some pitfalls.
>And with cryptography, these pitfalls can be _very_ hard to spot, even
>for "the clever guys".
I fully agree, but sometimes the application can have severe constraints that
prohibit the use of standard mechanisms. In these cases, you have a choice,
either you have little or no security, or you have to be inventive. However, if
you do invent a new protocol, it should undergo as much peer review as possible
before you consider implementing it. I am basically toying with different ideas
using RSA in severely constrained comms environments. I know that ECC and
variants are best suited to this but I would prefer if possible to stick to
RSA.
Mark
------------------------------
Subject: Re: RSA recoverable signature trick
From: [EMAIL PROTECTED] (Mark Currie)
Date: 11 Jan 2001 16:07:26 GMT
Thanks for the help, I will look up the references that you have quoted.
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Mark Currie wrote:
>> Years ago someone told be about a trick that you can pull when you want
>> to sign a public key of the same bit order.
>
>You cannot securely use the identity function as the encoding method for
>RSA signatures anyway, so don't try to do this. There is no getting round
>the fact that a secure recoverable signature of a piece of incompressible
>data will be longer than the original data (typically by *at least* 2t
>bits for a security level of 2^t). PSS-R achieves close to the minimum
>expansion for a provably secure method:
>
> Mihir Bellare, Phillip Rogaway,
> "The Exact Security of Digital Signatures: How to Sign with RSA and
> Rabin,"
> http://www-cse.ucsd.edu/users/mihir/papers/exactsigs.html
>
> IEEE P1363a draft version 6 (D6).
> http://grouper.ieee.org/groups/1363/P1363a/index.html
>
>PSS-R is unfortunately patented (and unlike the non-recoverable variant
>PSS, licensing is not free). Don't use the other standardised method for
>RSA signatures with message recovery, ISO/IEC 9796-1, because it is not
>secure against chosen-message attacks.
>
>- --
>David Hopwood <[EMAIL PROTECTED]>
>
>Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
>RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
>Nothing in this message is intended to be legally binding. If I revoke a
>public key but refuse to specify why, it is because the private key has been
>seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
>
>
>-----BEGIN PGP SIGNATURE-----
>Version: 2.6.3i
>Charset: noconv
>
>iQEUAwUBOlvUDDkCAxeYt5gVAQEFggf4lgLgf8JPOeXBPW85KKXnyKe8m/vZQfoU
>wEaTO85FnCv7iH9DVOhdgBylv7Bh/nwJRnQZhTeecMwl9i41lXBvmZ55Pb8CuU4m
>WODP/qhL8w3FYtQmxxibDgcTjLolrIngW6L1w/QWkZ3vvD6NBFCk/NNOIpuBNDv6
>bneNt9xpGfRNKmRjeN2WA8TRp2WxHBqnoRYw0TnHt7OrqS+nBmvRkmMmk+uto2WI
>xDwwxqqwfJsrUcy+IOTdcyjLTpIZyJ6sR81zaoIXoQI3eqFEYHf7qJvPXlzWSJLf
>RQQLz9IlyvQsQ6h9ySpVnTCwjK1XWSWIfdtu5mWFYTrOaFH/Ev3M
>=g0Qf
>-----END PGP SIGNATURE-----
>
>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES validation
Date: Thu, 11 Jan 2001 15:56:29 GMT
In article <93hlq0$k41$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi all
>
> Does anyone have some test vectors for DES. What a i really need is
> each of the keys used in each round...and some intermediate values for
> the first couple of rounds (like before sbox, after sbox). A single
set
> of key,plaintext and ciphertext will do but more than one would be
nice
>
Try http://www.geocities.com/custerstoe.geo/desecb.txt
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Thu, 11 Jan 2001 16:05:59 GMT
Greggy wrote:
> Take your pick, but reality is, they are dark and they have
> chosen we the people to be their next target.
That's not reality, it's a figment of a parnoid imagination.
I know many fine people who work for NSA, and they would not
participate in a domestic espionage program. Indeed, they
are trained in the requirement to obey the laws against such
activity.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 11 Jan 2001 17:39:48 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Greggy wrote:
>Specifically, that RSA is (practically speaking) impossible to verify
>the accuracy of the software, where ECC code is more intuitive and
>verifiable.
Huh? Could you elaborate? That's awfully counter-intuitive.
I think most people out there would say exactly the reverse
is true -- after all, there's a reason that one teaches RSA
(and not ECC) in the undergrad theory class. What am I missing?
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Thu, 11 Jan 2001 10:49:58 -0800
David Wagner wrote:
> Greggy wrote:
> >Specifically, that RSA is (practically speaking) impossible to verify
> >the accuracy of the software, where ECC code is more intuitive and
> >verifiable.
> Huh? Could you elaborate? That's awfully counter-intuitive.
> I think most people out there would say exactly the reverse
> is true -- after all, there's a reason that one teaches RSA
> (and not ECC) in the undergrad theory class. What am I missing?
I think the idea is that in any PK system, the hardest thing
to verify is that the private keys are generated properly.
There is no way to be sure that the random numbers are really
random, and no way for an external program to inspect the key
generation without revealing the most sensitive secrets.
In DH/DSA and ECC, private key generation is very simple because
it is just choosing an integer in a particular range. RSA is
a little more complicated because you have to generate primes.
If you follow ANSI, then the primes have some additional
requirements as well. Because the RSA private key generation
is more complex, there is more likely to be an accidental bug.
Choosing ECC system parameters is a lot more complicated than
anything in DH/DSA or RSA, but the parameters can be verified
externally without exposing any secrets.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Comparison of ECDLP vs. DLP
Date: Thu, 11 Jan 2001 18:49:38 GMT
David Wagner wrote:
>
> Greggy wrote:
> >Specifically, that RSA is (practically speaking) impossible to verify
> >the accuracy of the software, where ECC code is more intuitive and
> >verifiable.
>
> Huh? Could you elaborate? That's awfully counter-intuitive.
> I think most people out there would say exactly the reverse
> is true -- after all, there's a reason that one teaches RSA
> (and not ECC) in the undergrad theory class. What am I missing?
I am with you. I understand the RSA math, M^e mod N = C and C^d mod N
= M, is simple and elegant. I can teach it to any high-school student
(I admit that I do not understand how to find e, d and N for more than a
day at a time). I do not understand ECC math and have not encountered
anyone who can teach it to me.
The only part of RSA software that seems to me to obscure is the large
integer arithmetic software. While I understand what it does, how it
does it is fairly obscure. In the ECC case, I do not even understand
what it does; I must rely on authority.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: keeping secret keys secret
Date: Thu, 11 Jan 2001 18:56:32 GMT
isaac william oates wrote:
>
> Ladies and gentlemen,
>
> I'd like to create a web site for securely storing files and messages.
> The dilema that I'm faced with is that I need to store the secret key on
> the server and, unless there is a better way, secure that key with the
> password. The process that I'm thinking about is this:
>
> 1) when a new area is created, a 3DES key (area key) is created.
> 2) for each user with access, the area key is encrypted with their
> password.
> 3) when a user needs to add or retrieve information, I take their
> password, decrypt the area key, and do what I need to.
>
> So my problems are as follows:
>
> (a) I need to authenticate the user first. Can I use MD5 or will that
> make it too easy to crack someone's password? Once you've got someone's
> password, it's all over.
> (b) How long must the user's password be in order to keep the key safe?
> (c) What's better, a 112- or 168-bit 3DES key?
> (d) Is there a huge flaw here that I'm not seeing?
>
> I don't have much practical experience with cryptography, which probably
> doesn't make me the best person to write this software, but I'd like to
> have a go at it anyway.
>
> Thanks.
>
> Isaac Oates
Without knowing your application and environment, it is difficult to
comment.
However, the rule is, "Prefer tamper-resistant hardware for the storage
of secret keys." Providers of such hardware for web servers include
N-Crypt. Failing that, consider smart cards or a separate key-server
box.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: NSA and Linux Security
Date: Thu, 11 Jan 2001 19:13:25 GMT
"Douglas A. Gwyn" wrote:
>
> Greggy wrote:
> > Take your pick, but reality is, they are dark and they have
> > chosen we the people to be their next target.
>
> That's not reality, it's a figment of a parnoid imagination.
> I know many fine people who work for NSA, and they would not
> participate in a domestic espionage program. Indeed, they
> are trained in the requirement to obey the laws against such
> activity.
All of the many people that I know at NSA are exceptionally fine
people. That does not mean that the agency does not have an agenda and
it does not mean that fine people do not further agency agenda items
with which they disagree. I am prepared to grant you that NSA does not
engage in domestic espionage. I even grant you that they do not do
gratuitous domestic surveillance and that, partly in the name of
protecting sources and methods, they do not disclose the product of what
they do do. I wish that I was as confident that they do not profit from
the surveillance of US citizens by the other UKUSA countries. Perhaps I
am paranoid but I wish that I was confident that neither NSA nor UKUSA
product leaked to the FBI.
George Orwell warned us that bureaucrats, without motive or intent, do
what bureaucrats do. Lawrence Lessig warns us that as the price of
surveillance technology falls so does our freedom. I do not think that
it is paranoid to heed those warnings and behave accordingly. I have
spoken the same message in front of NSA people for two decades and have
yet to have one of them take offense.
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution
Date: Thu, 11 Jan 2001 19:15:33 GMT
Bryan Olson wrote:
>
> Douglas A. Gwyn wrote:
> > Paul Pires wrote:
> > > ... To me, It seems that:
> > > *if you can make a stream cipher that breaks the locational
> relationship
> > > between ciphertext, state and plaintext. AND
> > > *if you can make a stream cipher that automagically authenticates.
> AND
> > > *if you can do these things without loosing the speed and simplicity
> > > advantages......
> > > Then, it might just be interesting.
> >
> > Genuine stream ciphers (e.g. those long used by government)
> > often meet these requirements.
>
> Probably the most popular stream cipher in commercial use,
> (and also used by the government), is CBC-mode DES, probably
> followed by the other FIPS-approved modes of DES and 3DES.
> DES is a block cipher; the modes build a stream cipher from
> a block cipher.
And may reduce latency by generating the stream ahead while waiting for
input.
> --Bryan
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 11 Jan 2001 19:41:38 GMT
Subject: Re: Comparison of ECDLP vs. DLP
"I am with you. I understand the RSA math, M^e mod N = C and C^d mod N
= M, is simple and elegant. I can teach it to any high-school student
(I admit that I do not understand how to find e, d and N for more than a
day at a time). I do not understand ECC math and have not encountered
anyone who can teach it to me.
The only part of RSA software that seems to me to obscure is the large
integer arithmetic software. While I understand what it does, how it
does it is fairly obscure. In the ECC case, I do not even understand
what it does; I must rely on authority."
This is one of the "great con jobs" in PKI, in my humble opinion. It reminds
me of the novel 1984 even. If you repeat something long enough, people will
believe it.
What is the truth? The truth is that there is a LOT of sophisticated math
behind the RSA, DSA and ECC methods. All are operating in groups, but most
people do not know anything about group theory, nor do they want to and they do
not need to to do their jobs. So they rely on an expert, as they should.
For example, the RSA primitives (e.g., m**e mod n) are totally insecure when
considered by themselves. But many people get an ILLUSION of understanding by
seeing them and saying "hey, that is modular math, I can understand that." I
suspect most have NO IDEA why it works. A little knowledge is a dangerous
thing.
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: NSA and Linux Security
Date: Thu, 11 Jan 2001 20:39:39 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
Perhaps I
> am paranoid but I wish that I was confident that neither NSA nor UKUSA
> product leaked to the FBI.
>
>
by your reasoning, would you be reluctant to use a PGP dh/dss key just
because the SHA-1 was developed by the NSA?
{there is, in fact, a sizable minority of people who will use only RSA
keys [apart from the ADK issue ] primarily for this reason, but most
people are content with the scrutiny that SHA-1 has undergone by
experts in the cryptographic community, without finding a 'backdoor' in
the program.}
similarly, since the NSA version of Linux is open source, it is
reasonable to assume that if there were a backdoor in the program,
*somebody* of the very many capable people in the Linux community would
find it, gain instant fame, and the NSA would have a great deal of
uncomfortable explaining to do.
granted, that if they *could* put in a backdoor without worrying about
being found, they would be the people suspect to do so,
but as things go with open source, it doesn't seem worse than trusting
SHA-1, once some independent Linux experts approve the source code.
vedaal
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Thu, 11 Jan 2001 21:50:09 +0100
William Hugh Murray wrote:
>
[snip]
> George Orwell warned us that bureaucrats, without motive or intent, do
> what bureaucrats do. Lawrence Lessig warns us that as the price of
> surveillance technology falls so does our freedom. I do not think that
> it is paranoid to heed those warnings and behave accordingly. I have
> spoken the same message in front of NSA people for two decades and have
> yet to have one of them take offense.
The US doesn't have monopoly in modern surveillance technology
(certainly not today, if it ever did sometime in the past).
So, if one is worried about Orwell's scenario, one shouldn't
restrict one's view in any specific single direction but also
look around, I suppose.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 11 Jan 2001 20:54:21 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
DJohn37050 wrote:
>What is the truth? The truth is that there is a LOT of sophisticated math
>behind the RSA, DSA and ECC methods. All are operating in groups, but most
>people do not know anything about group theory, nor do they want to and they do
>not need to to do their jobs. So they rely on an expert, as they should.
>
>For example, the RSA primitives (e.g., m**e mod n) are totally insecure when
>considered by themselves. But many people get an ILLUSION of understanding by
>seeing them and saying "hey, that is modular math, I can understand that." I
>suspect most have NO IDEA why it works. A little knowledge is a dangerous
>thing.
Now wait just a second! You are changing the claim after-the-fact.
The original claim was that
``Specifically, that RSA is (practically speaking) impossible to verify
the accuracy of the software, where ECC code is more intuitive and
verifiable.''
You don't need to know much about the reasons why RSA is secure to verify
the accuracy of the software.
The claim was about *how* to implement RSA, not *why* it works. It seems
much easier to understand how to implement RSA than how to implement ECC.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 11 Jan 2001 20:59:08 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Roger Schlafly wrote:
>I think the idea is that in any PK system, the hardest thing
>to verify is that the private keys are generated properly. [...]
>
>In DH/DSA and ECC, private key generation is very simple because
>it is just choosing an integer in a particular range. RSA is
>a little more complicated because you have to generate primes.
Hmm. I see your point. Interesting observation.
But, I'm not sure I'm entirely persuaded. In ECC, you still have
to choose the group parameters and verify that the group order
is appropriate. Getting this code right (or verifying that it was
implemented correctly) seems more complicated than writing/verifying
code to generate primes.
(I was taught primality testing in my undergrad theory class, and I
think this is not at all unusual.)
It does seem to suggest an interesting research topic, though.
How can we structure cryptosystems to maximize the clarity and
assurance level of the implementation? This goes far beyond just
RSA vs. ECC.
------------------------------
** 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
******************************
