Cryptography-Digest Digest #784, Volume #9 Sun, 27 Jun 99 00:13:03 EDT
Contents:
Re: A few questions on RSA encryption (S.T.L.)
Re: trapdoor one way functions ([EMAIL PROTECTED])
Re: DES-NULL attack (Jerry Coffin)
Re: determining number of attempts required ([EMAIL PROTECTED])
Re: A few questions on RSA encryption ([EMAIL PROTECTED])
Re: determining number of attempts required ([EMAIL PROTECTED])
Re: A few questions on RSA encryption (S.T.L.)
Re: On an old topic of internet publication of strong crypto (JPeschel)
Re: Moore's Trend (Horst Ossifrage)
Re: A few questions on RSA encryption (Gilad Maayan)
Re: VIC cipher now described on web site (Uri Blumenthal)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: A few questions on RSA encryption
Date: 27 Jun 1999 01:13:43 GMT
I'm replying to multiple posters, just to let you know.
<<Well, for reasons of hardware limitations, I'm thinking of using a
relatively small RSA key. >>
What kind of hardware limitations? That must be pretty limited - I can have a
calculator (TI-89) that fits in my pocket (or a TI-92 if I have slightly larger
pockets... :-D ) perform RSA with a 300-decimal-digit key, approximately a
1024-bit keysize! Of course, it's not *that* speedy.
I said:
<<Therefore, the strength of your resulting encryption... how well the
symmetric cipher "hides" the munged keyseed.>>
Someone replied:
<<Hold on, the symmetric cypher isn't hiding the keyseed - the keyseed
is out in the open (in plaintext form). If it wasn't, you wouldn't be
able to decrypt the message, and it would be pretty much useless. If
I'm not mistaken.>>
By what I said, I was referring to how difficult it is for the Adversary to
determine the *munged* keyseed used in the symmetric encryption, based on the
ciphertext. The Adversary knows the non-munged keyseed, the symmetric
algorithm, and the ciphertext. Apparently (according to the original poster),
the Adversary does not have the plaintext. However, what the original poster IS
concerned about is the security of the munging process, not the plaintext
itself. That's a little odd, of course. When I referred to how well the
symmetric cipher "hides" (see the quotation marks?) the *munged* keyseed, I
meant exactly what I stated in the first sentence of the paragraph. The
Adversary must FIRST determine the *munged* keyseed (which he does not know)
from the symmetric encryption algorithm and the ciphertext, BEFORE comparing
the *munged* keyseed with the keyseed he already knows, IN ORDER to determine
the munging process, which is what the original poster is concerned about. Or
maybe I'm wrong - the last question was quite complex and not a very common
one.
<<You can't keep the modulus secret. So that's not an option.>>
Why not? A little experiment:
We have two friends: Al and Bob. They each can do RSA. Al prepares a modulus,
and a secret key for himself and the corresponding public key. He gives the
modulus and the public key to Bob, *securely*, just like he would give Bob an
IDEA key securely. Bob does the same for Al. Now, Ezekiel enters the room, and
prevents any secure communication (but does not, of course, compromise the
security of their individual computers). Al and Bob can, however, send messages
encrypted with RSA, and Ezekiel has no idea what the modulus is.
Now, OBVIOUSLY, keeping the public key and modulus a secret prevents
transmission of RSA keypairs over non-secure lines, making RSA effectively just
like a symmetric cipher. But stronger, I say, because of it. :-D Of course,
this would be unsuitable for an application like PGP, which lets users fully
enjoy the advantages of asymmetric cryptography.
<<Brute force of the private exponent? Are you nuts they are normally 512
bits!!!>>
I said extremely difficult, and then I said I could not *quantify* it. What is
your problem with that? 512 bits seems "extremely difficult" to me. I never
said "extremely difficult but feasible", which is what you interpreted it as.
<<there are two many plaintext/ciphertext blocks to make this practical.
I think for 1024-bit keys it's around 40 byte blocks, which means 2^320
possible blocks!!!>>
Um, duh. That's why no one really worries about chosen-plaintext attacks as
long as the message is not extraordinarily small. That's why RSA is considered
secure. You keep thinking I mean that these attacks are practical, which they
(in general use) most certainly are NOT.
<<In RSA the modulus is public, it's factors are not. That's where the
security (supposedly) comes from.>>
Of course. But keeping the modulus secret improves security somewhat, with the
associated disadvantages of more difficult use. Why reveal anything that you
don't *have* to, if your algorithm is good? (Attention: NOT an argument for
keeping algorithms secret, you see.)
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #2: Thou Shalt Conserve Mass/Energy In Closed Systems.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: trapdoor one way functions
Date: 26 Jun 1999 20:42:59 -0400
[EMAIL PROTECTED] wrote:
> I was wondering if there are any other trapdoor one way functions in
> academia that don't use either the discrete logarithm problem or the
> integer factoring problem.
I recall vaguely a press release from about 8 months ago about IBM coming
up with an algorithm based on a combinatorial problem rather than a number
theory problem (the press release had no details, of course).
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: DES-NULL attack
Date: Sat, 26 Jun 1999 19:46:21 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ predictions about the end of Moore's "law" ]
> Yeah, but the "past predictions" were based on technical difficulties,
> the new predicions are based on physical laws.
Nearly all of them were seen as physical laws until somebody found a
way around them.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: determining number of attempts required
Date: Sun, 27 Jun 1999 02:07:19 GMT
In article <7l3rpd$5m5$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Keith A Monahan) wrote:
> Ok, so the formula is (possiblechars) ^ (numberofchars), and then
divide
> by the number of (possiblechars-unique chars). Right?
m! / n!
Where m is the max or upper limit and n is the lower limit. You said
there was 35 chars, m = 35, and there are 12 in the password. If one
of them repeat you get (n = m - 12 or n = 23)
35*33*..*1 but all coefficients from m-12 to 2 are not present, so you
get m! / n! or 35! / 23!. Which is
35*34*33*32*31*30*29*28*27*26*25*24.
>
> Yeah, I think I could probably trim the list down, and it looks like
I'm
> going to have to. As far as password crackers ( I haven't seen a
Blowfish
> one) and dictionary attacks, I don't see much luck there. I'm sure
the
> password does not have more than one English word in it, and the
symbols
> involved would probably throw most crackers anyways.
Well dictionary attacks normally try patterns of words. Say you have a
list of 1000 common words, and you know the password is only 5 words
max. You have 1000! / 995! or about 990034950024000 possible passwords
(2^49.98). Most attacks work like this, however you normally try to
reduce the word list. For most people about 250 words are probable
(related to them or their work). This makes 250! / 245! or 2^39, which
is about a days worth of work.
> The password picked (by me, if you must know) was designed
specifically
> to resist attacks :)
Hmm why may I ask are you trying to hack your own password?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: A few questions on RSA encryption
Date: Sun, 27 Jun 1999 02:24:41 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (S.T.L.) wrote:
> What kind of hardware limitations? That must be pretty limited - I
can have a
> calculator (TI-89) that fits in my pocket (or a TI-92 if I have
slightly larger
> pockets... :-D ) perform RSA with a 300-decimal-digit key,
approximately a
> 1024-bit keysize! Of course, it's not *that* speedy.
It's not that speedy on many computers so don't feel bad.
> <<You can't keep the modulus secret. So that's not an option.>>
>
> Why not? A little experiment:
Why not because people could not use your *public* key to encrypt you
messages. If you keep all the info private why not use a symmetric
cipher? That's the point of PKC.
To keep the modulus private I would just send the keys in private and
not upload them. That way only you two can send messages. But then
why use PKC?
> <<Brute force of the private exponent? Are you nuts they are
normally 512
> bits!!!>>
>
> I said extremely difficult, and then I said I could not *quantify*
it. What is
> your problem with that? 512 bits seems "extremely difficult" to me. I
never
> said "extremely difficult but feasible", which is what you
interpreted it as.
Actually we're wrong. You only have to search the prime factors of n =
pq. That's not 2^512 work (although it may seem like it).
> Um, duh. That's why no one really worries about chosen-plaintext
attacks as
> long as the message is not extraordinarily small. That's why RSA is
considered
> secure. You keep thinking I mean that these attacks are practical,
which they
> (in general use) most certainly are NOT.
Well PKCS #1 defines the padding does it not? I really should read
that standard....
> Of course. But keeping the modulus secret improves security somewhat,
with the
> associated disadvantages of more difficult use. Why reveal anything
that you
> don't *have* to, if your algorithm is good? (Attention: NOT an
argument for
> keeping algorithms secret, you see.)
Keeping the modulus private does not make it any more secure. The
security of RSA is based on the difficulty of finding the FACTORS of n
= pq. not n. If you can factor pq into p and q you can find the
private exponent. By keeping the modulus private you make PKC a
trivial waste of time.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: determining number of attempts required
Date: Sun, 27 Jun 1999 02:18:43 GMT
In article <7l3rpd$5m5$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Keith A Monahan) wrote:
> Ouch. 2^61 and 2^50 are awefully big numbers :) Especially when you
divide
> by 2000/hr, that's alot of hours.
Note that you can spread this search among other computers! You can
divide the space for example among 32 computers to expect to find it in
about 2^55 and 2^44 trials respectively.
If you can trim the list down to say 16 letters (?) you will get a
search of 2^39.66 and expect to find it in about 2^33 trials on the
network. That's a modest amount of work but assumes you can limit the
search to only 16 chars (a 12 letter password with unique chars). At
your rate you would find it in about 2^26 hours or 7660 years which is
out of the question. With 32 computers would expect to find it in 2^21
hours or 239 years...
Obvious the rate of 2^12 an hour is too low. Given you could try about
2^15 passwords a second (speedy pentium), you could search the space in
about 2^23 seconds or 97.09 days. On the 32 computer network that
would be 2^18 seconds or 3.03 days.
That's just some number though, it depends on the implementation.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: A few questions on RSA encryption
Date: 27 Jun 1999 03:06:58 GMT
<<Why not because people could not use your *public* key to encrypt you
messages. If you keep all the info private why not use a symmetric
cipher? That's the point of PKC.
To keep the modulus private I would just send the keys in private and
not upload them. That way only you two can send messages. But then
why use PKC?>>
Because RSA would still rely on the problem of factoring integers. But you're
right, it's not THAT useful.
<<Actually we're wrong. You only have to search the prime factors of n =
pq. That's not 2^512 work (although it may seem like it).>>
Did I say that it was 2^512 work? Nope. I said that it was "extremely
difficult". Not something your home computer can do... yet.
<<Well PKCS #1 defines the padding does it not? I really should read
that standard....>>
I never mentioned anything about padding (which would, of course, protect
little plaintexts).
<<Keeping the modulus private does not make it any more secure. The
security of RSA is based on the difficulty of finding the FACTORS of n
= pq. not n. If you can factor pq into p and q you can find the
private exponent. By keeping the modulus private you make PKC a
trivial waste of time.>>
How can you factor a number when you don't know what it is in the first place?
That's my point. But keeping the modulus secret does make RSA effectively a
secret-key system.
By the way, I am aware of why RSA is difficult. I coded an RSA program for my
TI-92. While I can't understand the actual mathematics behind WHY it works (why
the generation method gives the keypair the properties it has), I know *how* it
works.
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^3021377 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Great SRian
Conspiracy, the Triple-Sigma Club, and the Union of Quantum Mechanics
Avid watcher of "World's Most Terrifying Causality Violations", "World's
Scariest Warp Accidents", and "When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #2: Thou Shalt Conserve Mass/Energy In Closed Systems.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: On an old topic of internet publication of strong crypto
Date: 27 Jun 1999 03:29:37 GMT
>Mok-Kong Shen <[EMAIL PROTECTED]> writes:
>> Not necessarily. If you were talking about software rather than
>> something like a scientific paper, it doesn't matter to the US
>> that it came from elsewhere: once you bring it in you can't send
>> it back out.
>
>Your point is new to me. But why should a scientific paper possibly
>be subject to higher degree of restriction than software (which
>implements the idea in the paper), rather than the other way round?
>
That's not what he said. A scientific paper is not subject to export
restriction.
You can get descriptions, for instance, of all of the AES from a US government
site no matter where you live.
http://csrc.nist.gov/encryption/aes/aes_home.htm
The electronic distribution of source code, however, is restricted.
If do not live in the US or Canada, and if you want, however, you may submit a
request to NIST for a CD with AES source. NIST will make an application
for the export license for you.
******
To paraphrase EAR, anytime you export code outside of the US or Canada (or
by making it available on the 'net) it's exportation. It doesn't matter
whether
the code was imported first.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Horst Ossifrage <[EMAIL PROTECTED]>
Subject: Re: Moore's Trend
Date: Sat, 26 Jun 1999 20:38:17 -1000
(was des null key thread)
William Tanksley wrote:
> Mind you, I'm not arguing that Moore's law will continue to apply --
> I'm arguing that it's not wise to design encryption with anything
> else in mind.
>
> --
> -William "Billy" Tanksley
If Moore's Trend continues, it will take 120 years before
a $250,000 computer can test all 128 bit keys in one day.
It will be 300 years for 256 bit keys.
If runners continue increasing their speeds at the rate they
are now, women will break the sound barrier before men.
------------------------------
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: Re: A few questions on RSA encryption
Date: Sun, 27 Jun 1999 03:36:59 GMT
Tom, thanks for your reply, but there's no need to be condescending. I
understand the algorithm just as well as you do. In reply to some of
your points -
1. Yes, it is possible to keep a modulus secret, and share it only
with the intended receiver, as in secret key cryptology. You would
have some key-management issues to deal with, but if you wanted to,
you could.
2. Yes, it is possible to keep a public key secret, as above. Once
again, key-management is a problem, but I'm aware of that.
3. Of course this is an unconventional use of the algorithm, but that
doesn't necessarily mean I "don't seem to know the algorithm." It just
means I have an unconventional application. Have you thought of that?
4. At the end of the day, you didn't really answer any of my
questions, which would have been nice. You just said "Moduluses aren't
kept secret in RTS, stupid," over and over again. Which is a shame,
because you seemed to be very knowledgable about the subject, and
probably could have helped me out.
Gilad Maayan
------------------------------
From: Uri Blumenthal <[EMAIL PROTECTED]>
Subject: Re: VIC cipher now described on web site
Date: Sat, 26 Jun 1999 23:59:42 -0400
Reply-To: [EMAIL PROTECTED]
John Savard wrote:
> >That cipher must have been a Soviet red herring. There is no
> > way to implement a hand cipher of that complexity.
I strongly disagree, and my experiments with VIC were quite
successful.
> I'll admit that carrying out chain addition for such a length of
> time seems to be impossibly prone to error.
Well, maybe for a modern public-school graduate (:-).
Seriously, it is not half as bad as it seems. In
fact, it is very easy.
The real hard part [for me] was to memorize the exact sequence
that LEADS to chain-addition step. According to Kahn, it was
hard enough for Heihannen (or what was his name?) that he
took a written description of the cipher with him! But
he didn't worry about his [in?]ability to perform
about 50 additions without error.
> However, when you have the ability to send people to Siberia, it's
> surprising what skills you can get them to learn.
Absolutely true! (:-)
Actually, it seems that you don't even need a threat of Siberia
to teach a man to add correctly single-digit numbers! (:-)
--
Regards,
Uri
-=-=-==-=-=-
<Disclaimer>
------------------------------
** 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
******************************
