Cryptography-Digest Digest #783, Volume #9 Sat, 26 Jun 99 21:13:03 EDT
Contents:
Re: RSA msg length... (Gilad Maayan)
Re: A few questions on RSA encryption (Gilad Maayan)
Re: A few questions on RSA encryption ([EMAIL PROTECTED])
Re: Kryptos article (Jim Gillogly)
Re: Moores Law (a bit off topic) ([EMAIL PROTECTED])
trapdoor one way functions ([EMAIL PROTECTED])
Re: Tough crypt question: how to break AT&T's monopoly??? ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
determining number of attempts required (Keith A Monahan)
Re: DES-NULL attack (JPeschel)
Re: A few questions on RSA encryption ([EMAIL PROTECTED])
Re: determining number of attempts required ([EMAIL PROTECTED])
Re: A few questions on RSA encryption ([EMAIL PROTECTED])
Re: determining number of attempts required (Keith A Monahan)
Re: RSA msg length... ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: Re: RSA msg length...
Date: Sat, 26 Jun 1999 21:18:19 GMT
Okay, but what happens if the message is much smaller than the key?
Say I'm trying to encrypt 20 bits with a 512 or 1024-bit key. Would I
be able to?
------------------------------
From: [EMAIL PROTECTED] (Gilad Maayan)
Subject: Re: A few questions on RSA encryption
Date: Sat, 26 Jun 1999 21:49:27 GMT
>Okay, why involve RSA? If you are assuming that the Adversary has broken it,
>why not *simplify* your scenario and have the keyseed sent in the clear? (We
>can have absurd situations!)
Well, for reasons of hardware limitations, I'm thinking of using a
relatively small RSA key. So it will be a bit difficult for your
casual attacker to break it, but a more determined analyser might get
through it, and find this second layer.
>Therefore, the strength of your resulting encryption... how well the symmetric cipher
>"hides" the munged keyseed.
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.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: A few questions on RSA encryption
Date: Sat, 26 Jun 1999 22:16:21 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gilad Maayan) wrote:
> 1. I haven't been able to find any information on the relationship
> between the number of bits encrypted by RSA, and the level of security
> obtained. Let's say you're encrypting 20 bits with a 512 or 1024 bit
> key. Is the small size of the plaintext relevant? Will the encrypted
> message be easier to crack than, say, an entire document encoded by
> the same RSA key?
Well I think PKCS #1 covers this and it should be <= half the modulus
size if I am correct. I am not sure why you would have to read the
standard. AC covers it as well.
Also the size of the private exponent/modulus will effect the safety of
the key. A smaller exponent/modulus will be easier to factor and thus
find the private key.
> 2. Would it be at all possible to break an RSA cyphertext, knowing
> neither the secret key, the public key, or the modulus?
If you know the secret exponent and the modulus (the modulus is public)
then one could decrypt the ciphertext easily.
> 3. Would it be possible to extrapolate an RSA key from a cyphertext,
> if the plaintext was known? (assuming that neither the key used for
> encryption nor its corresponding modulus are known).
The plaintext is always known for the attacker. That's because the
keys are public/private. So I would assume the answer is no.
> 4. If the modulus and public key were known, would available
> cyphertext-plaintext make the cryptoanalysis process faster or easier?
The modulus is always known. The factors are not however.
I don't think you understand the algorithm to well. I don't know the
theory but I do know how it works.
You have p and q which are prime. The modulus n = pq is public but p
and q are not. e is the private exponent C = P^e mod pq, and the d is
the public exponent P = C^d mod pq.
Basically (pq, d) = public, (p, q, e) = private. You don't need to
keep p and q after the keys are generated however.
The most common method of attack is to factor pq into p and q. If you
can do this you can somehow find e from g^d mod pq.
Remember that public key crypto is different then secret key crypto.
The attack will have unlimited access to chosen plaintexts because they
will have the encrypting key. Therefore the security is solely on the
difficulty of finding the decrypting key. In RSA this is as difficult
as factoring large composites (well that's a conjecture but...). Just
like in Diffie-Hellman the security comes from finding the discrete
logarithms.
There are attacks where the modulus is too small, and attacks where e
or d are to small. I would read a good description of RSA before, as I
may have some facts off...
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: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Kryptos article
Date: Sat, 26 Jun 1999 15:35:48 -0700
B & J wrote:
>
> I got quite interested in this KRYPTOS code thing, and was able to find the
> keys for the first
> 2 parts, but does anyone know if the keys mean anything at all , perhaps
> encrypted ? seems like gibberish to me....
Yes -- if you set it up like a matrix, with the KRYPTOSABC...
keyword across the top as the plaintext alphabet, and each
offset KRYPTOSABC... keyword underneath it at the right offset
so that the 1st ciphertext letter is below the corresponding
plaintext letter in the top alphabet, you will be able to read
whichever keyword you recovered in a vertical line somewhere
in the matrix.
Look under the K to find the keyword Jim Sanborn used when he
encrypted the section. Each is an English word.
--
Jim Gillogly
Trewesday, 3 Afterlithe S.R. 1999, 22:28
12.19.6.5.11, 2 Chuen 19 Zotz, Third Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Moores Law (a bit off topic)
Date: Sat, 26 Jun 1999 22:54:01 GMT
In article <[EMAIL PROTECTED]>,
Horst Ossifrage <[EMAIL PROTECTED]> wrote:
> Gorden Moore, former Chairman of the Board of Intel Corporation
> once said that the trend was that microprocessor performance
> doubled every 18 months. He did not say it is a law. There is not much
> more than that to research for you. You can just find the date
> he said it, and where he was quoted. It was an observation of his,
> not a calculation based on fundamental causes. The causes of this
> doubling of performance has been discussed in the IEEE Journal of
> Solid State Circuits and in the Digest of Technical Papers of
> the "International Solid State Circuits Conference" (ISSCC).
> IEEE stand for the Institute of Electrical and Electronics
> Engineers. See www.ieee.org
Thanks for the summation. That was quick!
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: trapdoor one way functions
Date: Sat, 26 Jun 1999 23:03:09 GMT
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.
Basically I would like to research puzzles which are not 'large' number
oriented (which would dismiss ECC as well).
If anyone has any hints, links or ideas please let me know.
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: Tough crypt question: how to break AT&T's monopoly???
Date: Sat, 26 Jun 1999 22:57:24 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (S.T.L.) wrote:
> Therefore a sort of mini-decryptor program needs to be attached to the
> cyphertext, just as self-extracting ZIP files have a mini-extractor
attached to
> the cyphertext.
>
> Or, one could hack a version of PKZIP to use strong cryptography.
One could always pick up Blowfish/ZLIB and make a cool archive
zipper/encipherer. (wait PGP already exists, albeit it doesn't use
blowfish but you get the point).
ZLIB is a cool lib, and I would suggest to check it out for any file
crypto program.
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: DES-NULL attack
Date: Sat, 26 Jun 1999 23:00:02 GMT
In article <gZbd3.21721$[EMAIL PROTECTED]>,
"Mike Murray" <[EMAIL PROTECTED]> wrote:
> Aernst, if you have repeatedly broken RSA (as your page suggests),
> and you have broken DES, why have you yet to publish these results?
>
> BTW, your "proofs" of your breaks of RSA are vague, to say the
> least... unless I'm missing something that you've assumed (you assumed
> a hell of alot, IMO)...
>
> Perhaps you could explain them to me, or, at least, make them a
> little clearer...
Well his claims are far fetched. DES is not broken by the NULL
attack. It is however not a good algorithm to use now...
His attack on RSA is way out left field. Unless he has formal examples
of his claims I wouldn't trust him. RSA however is falling a bit since
1024 bit keys are now the minimum...
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] (Keith A Monahan)
Subject: determining number of attempts required
Date: 26 Jun 1999 22:40:42 GMT
Hi there,
Haven't been following the group like I used to, but glad to see the same
names out here!
I'm trying to figure out the total number of attempts required to attack
a given password. I have alot of information about the password, which
is beneficial in reducing the total keyspace to search.
I have this information about the password :
1. Password consists of lower case letters, the symbol set consisting of
8 choices(I know the choices), and one space.
This puts my total character set to 35. Not too, too bad in comparison to
255 possibilities like normal ASCII.
2. There are no repetitous characters in the password except one case.
One of two possible characters is repeated one time. Those characters are
known.
3. The password is between 8 and 14 characters in length. If length
drastically affects the answer, I believe it to be close to 12 characters.
I have to write a program which tries all those possibilities, so I also
need to know how to effectively reduce the set down to within those
limitations. I dont believe I can simply iterate through all the
possibilities, simply discarding non-matches before I try them, because of
the immense time it would take. I know how to limit my attempts to certain
characters, but that repetition thing has me stumped. Is there a way
to generate only all original(no identical characters within the same string)
keys?
The bad news is I can only try about 1500-2000 attempts per hour because
of the limitations of my input device. I cannot attack the cyphertext
directly, as I don't believe there are any attacks better than bruteforce.
Algorithm is 256-bit Blowfish. Some plaintext is known and my attempts/sec
could be increased drastically if there was already a custom Blowfish
brute-force attacker(none that I know of).
Last bit of bad news is that I'm bad at math, but certainly willing to apply
myself. The answer is important but the formulas would be great if I could
learn how to use them. C code is certainly welcome, too!
Thanks for taking the time to help,
Keith M.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: DES-NULL attack
Date: 26 Jun 1999 23:47:34 GMT
>[EMAIL PROTECTED] writes:
> RSA however is falling a bit since
>1024 bit keys are now the minimum...
The report I think you get your "minimum" estimate from also
mentions "for short-term authenticity purposes 512 Bit
might suffice in this century." Just an observation. I wonder
about 768-bit keys. Keys of that size seem pretty safe for
quite a few years, barring a factoring breakthrough.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: A few questions on RSA encryption
Date: Sat, 26 Jun 1999 22:38:45 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (S.T.L.) wrote:
> I am not sure. Probably not. There are a heck of a lot possible
keypairs, and
> not knowing even the modulus makes it worse for the Adversary.
Keeping even the
> public key-and-modulus secret has to improve security, but I'm not
sure by how
> much.
You can't keep the modulus secret. So that's not an option.
> Possible (brute-force) but extremely difficult, I'm guessing. I can't
quantify
> HOW difficult, though.
Brute force of the private exponent? Are you nuts they are normally >=
512 bits!!!
> Of course not, the Adversary already has an infinite supply of ready-
on-demand
> ciphertext-plaintext. :-D Think about it - the Adversary, using the
public key
> and modulus can encrypt any darn plaintext he feels like and look for
the
> ciphertext. Now, as to whether analyzing ciphertext-plaintext pairs
would be of
> any help, I don't *believe* so, but I'm not sure.
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!!!
In RSA the modulus is public, it's factors are not. That's where the
security (supposedly) comes from.
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: Sat, 26 Jun 1999 23:43:00 GMT
Well it's a max of
35^n where n is the number of chars. So for your guess of 12 this
would be 3379220508056640625 or 2^61 guesses. Obviously out of reach.
You said that all the chars are unique except for 2, which means you
have about 35! / 23! or about 2^58 guesses (for 12 char passwords) this
is because there are 35*34*33*32...*24 possible passwords to use if no
char is repeated.
If you could find out which chars are definately not goings to be
apparent you could reduce the search much more. Think of maybe 24
chars that would be used, then there would be only 24! / 12! or 2^50
guesses...
I would most likely use a dictionary attack if you the types of
words/punctuation in the password. I might be off in some of the
numbers (I have not done finite yet) but I would check up on passwd
crackers on the net. Most programs will work for badly chosen
passwords...
Tom
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: Sat, 26 Jun 1999 23:47:27 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gilad Maayan) wrote:
> 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.
The purpose of PKC is to share a private key with only the intended
recipient. In most models you will make a random session key (for a
cipher like RC4, CAST, etc...) then encrypt the message with the
symmetric cipher. The session key is then encrypted with the public
key. Only the owner of the private key can retrieve the session key
and read the file.
Not even the sender can decrypt the session key, which implies an
attacker should not be able to as well.
If you send the session key in the clear what's the point?
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] (Keith A Monahan)
Subject: Re: determining number of attempts required
Date: 27 Jun 1999 00:38:05 GMT
Tom,
Ouch. 2^61 and 2^50 are awefully big numbers :) Especially when you divide
by 2000/hr, that's alot of hours.
Ok, so the formula is (possiblechars) ^ (numberofchars), and then divide
by the number of (possiblechars-unique chars). Right?
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.
The password picked (by me, if you must know) was designed specifically
to resist attacks :)
Thanks for your quick response,
Keith
[EMAIL PROTECTED] wrote:
: Well it's a max of
: 35^n where n is the number of chars. So for your guess of 12 this
: would be 3379220508056640625 or 2^61 guesses. Obviously out of reach.
: You said that all the chars are unique except for 2, which means you
: have about 35! / 23! or about 2^58 guesses (for 12 char passwords) this
: is because there are 35*34*33*32...*24 possible passwords to use if no
: char is repeated.
: If you could find out which chars are definately not goings to be
: apparent you could reduce the search much more. Think of maybe 24
: chars that would be used, then there would be only 24! / 12! or 2^50
: guesses...
: I would most likely use a dictionary attack if you the types of
: words/punctuation in the password. I might be off in some of the
: numbers (I have not done finite yet) but I would check up on passwd
: crackers on the net. Most programs will work for badly chosen
: passwords...
: Tom
: Sent via Deja.com http://www.deja.com/
: Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA msg length...
Date: Sat, 26 Jun 1999 23:44:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gilad Maayan) wrote:
> Okay, but what happens if the message is much smaller than the key?
> Say I'm trying to encrypt 20 bits with a 512 or 1024-bit key. Would I
> be able to?
Yes, but you should pad the message according to PKCS #1.
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: DES-NULL attack
Date: Sun, 27 Jun 1999 00:52:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (JPeschel) wrote:
> The report I think you get your "minimum" estimate from also
> mentions "for short-term authenticity purposes 512 Bit
> might suffice in this century." Just an observation. I wonder
> about 768-bit keys. Keys of that size seem pretty safe for
> quite a few years, barring a factoring breakthrough.
My PGP DH keys are 4096 bits. This is because well I don't feel like
making new keys anytime soon. This is under two assumptions though.
1) No breakthrough will be able to find the DL of a 4096-bit number any
time soon
2) PGP's implementation is correct.
The latter I trust. I think #1 is ok now for a long time as well.
Speaking of which does anybody have a good paper on DLP or diffie-
helman?
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.
------------------------------
** 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
******************************
