Cryptography-Digest Digest #799, Volume #8 Sat, 26 Dec 98 12:13:03 EST
Contents:
symmetric encryption with a user-supplied password ("denis bider")
Re: Encrypt 98 (JPeschel)
Re: symmetric encryption with a user-supplied password (Nathan Kennedy)
Transforming DES into a non-Feistel cipher
Re: symmetric encryption with a user-supplied password (wtshaw)
Re: What is "group" means in block cipher ? (fungus)
Re: Transforming DES into a non-Feistel cipher (Harpy-19)
Re: [Q. newbie] Authentication/Digital Signatures (Harpy-35)
[Q. newbie] Authentication/Digital Signatures (Thomas Harte)
Re: [Q. newbie] Authentication/Digital Signatures (Nathan Kennedy)
Re: symmetric encryption with a user-supplied password (Harpy-34)
Re: symmetric encryption with a user-supplied password (fungus)
Re: Transforming DES into a non-Feistel cipher
Re: Session keys in Elliptic Curve (Anonymous)
----------------------------------------------------------------------------
From: "denis bider" <[EMAIL PROTECTED]>
Subject: symmetric encryption with a user-supplied password
Date: Sat, 26 Dec 1998 03:25:38 GMT
I stumbled upon a topic that I have not yet seen discussed: when data is
being encrypted with a password supplied by the user, for instance by
128-bit RC5, how do you create a key that indeed contains 128 bits of
entropy?
Well, since the encryption should depend solely on the user's password, it
follows that the secret key cannot have more entropy than that password.
Therefore, the user should somehow be forced to use a password with that
much entropy.
Normally, poorly educated users will choose passwords of about 6 bytes in
length, containing mostly lowercase letters. This provides us with only 19
bits of entropy, which is ridiculous. Now, we can make the user choose a
password that contains at least one uppercase letter and at least one digit
and we can enforce a minimum length of 10 bytes. This brings the entropy up
to about 59 bits - but that is still far from enough. At least 70 and
preferrably 90 bits was recommended in 95/96, therefore we will be safe with
75-95 today.
My guess is that, to really provide 128-bit-strong encryption, you would
have to ask the user to choose a password about 22 bytes in length. The
alternative would be to have the user remember 16 random bytes in the range
0..255. Both of these solutions are rather uncomfortable for the user.
But if we don't do this, any pedestrian hacker will be able to break the
encryption in a week.
Can anybody think of a method for raising the entropy of the password
without straining the user into remembering kilobyte-long streams of random
data?
--
denis bider ([EMAIL PROTECTED], [EMAIL PROTECTED])
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Encrypt 98
Date: 26 Dec 1998 05:27:23 GMT
><[EMAIL PROTECTED]>writes:
>Have someone a statement to this encryption program?
>
If you post the URL, someone might offer a statement, an
opinion, a rant or a rave.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Nathan Kennedy <[EMAIL PROTECTED]>
Subject: Re: symmetric encryption with a user-supplied password
Date: Sat, 26 Dec 1998 13:38:24 +0800
denis bider wrote:
> Can anybody think of a method for raising the entropy of the password
> without straining the user into remembering kilobyte-long streams of random
> data?
The fact is, the more entropy, the more data, the more difficult the
key is to remember. No matter what, a stronger passphrase for a
stronger key will always be harder to memorize. The fact is,
memorizing 128 bits of entropy is never going to a simple task. It
would take a good deal of practice to remember that much.
Basically, it comes down to, do you want to spend a LOT of effort
memorizing a high-entropy key (128 bits is a lot to memorize be it in
base 64, hex, or English), which in most cases simply won't happen, to
memorize a low-entropy key (which may be easier to guess), or to pick
a truly random key and store it in a Safe Place (write it down and
hide it, keep it on a guarded floppy in on ones person or something).
The situation determines what is most appropriate, but I guess for
most high-security situations the last is most practical/secure. Keep
in mind that losing a key can be as disastrous (or more so) than that
data being compromised.
Nate
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Transforming DES into a non-Feistel cipher
Date: 26 Dec 98 06:34:17 GMT
I had been pondering whether or not it was possible, by a suitable choice
of transformation, to change DES into an equivalent cipher of the form:
XOR subkey
unkeyed transformation on block
XOR subkey
unkeyed transformation on block
...
when I finally realized the 'trick' that was needed. The F-function uses
certain bits from the right half of the block as XORed with two different
subkey bits. So, to have the extra copy of the bits that is needed,
subject the plaintext block to the initial permutation - and then subject
both halves to the expansion permutation, and treat DES as a block cipher
with a 96-bit block size.
The unkeyed transformation is the XOR of the left half with the f-function
of the right half; before and after it, XOR the right half with the
current subkey. Instead of swapping halves, one alternates between two
unkeyed transformations.
And then I realized that since each transformation only XORs one half with
a function of the other half, the half that is being XORed need not have
its correct value; another XOR can happen early or late.
Thus, I realized that it is possible to combine pairs of rounds, so that
there is only one unkeyed transformation, applied eight times, with nine
XORs of key material.
This may be made slightly clearer by listing what the nine new 96-bit
subkeys consist of:
(S2,S1)
(S2 XOR S4,S1 XOR S3)
(S4 XOR S6,S3 XOR S5)
(S6 XOR S8,S5 XOR S7)
...
(S14 XOR S16,S13 XOR S15)
(S16,S15)
and at the end, one swaps halves, discards duplicate bits, and does IIP.
It may be that this transformation was seen as obvious by people doing
early analysis of DES, and the reason I hadn't seen it mentioned was
because it did not help to simplify cryptanalysis.
John Savard
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: symmetric encryption with a user-supplied password
Date: Fri, 25 Dec 1998 23:14:02 -0600
In article <SGYg2.85$[EMAIL PROTECTED]>, "denis bider"
<[EMAIL PROTECTED]> wrote:
>
> Can anybody think of a method for raising the entropy of the password
> without straining the user into remembering kilobyte-long streams of random
> data?
>
I don't know about you, but when in school, we learned long poetic
passages for some courses, and memorized other texts and speeches for
others. If I can do that, you can remember a sentence sufficiently long
enough to contain as much randomness as you need. It would probably be
best for the hashing routine to be cut especially for the purpose, cutting
out differences that might be from capitalization and punctuation
errors.
To do this, remembering something long enough, it amounts to one thing for
the user, discipline.
--
What goes around, comes around.
You reap what you sow.
Do unto others as you would have them do unto you.
The wheels of the gods grind most slowly, but exceedingly fine.
People in glass houses should not cast stones.
Let those who are without sin cast the first stone.
Judge not that ye be judged.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: What is "group" means in block cipher ?
Date: Sat, 26 Dec 1998 09:04:19 -0100
Seung-Chul, Chae wrote:
>
> Someone said, DES encryption generates a semigroup and other
> encryption generates a group.
> What is "group" means ? it is a set of block ?
Imagine you encrypt some data twice with seperate keys K1 and K2
If there exists a single key K3 which can decrypt the data then
the encipherment is a group.
In DES this is not possible. You may find one key which will decrypt
one block of data, but it would be luck. You probably won't even be
able to decrypt other blocks of the same message.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Harpy-19 <[EMAIL PROTECTED]>
Subject: Re: Transforming DES into a non-Feistel cipher
Date: Sat, 26 Dec 1998 04:33:42 -1000
In the title "Transforming DES into a non-Feistel cipher" a premise was
established. But then, your description produces a Feistel cipher by
using left and right halves that are XORed. The main advantage of a
Feistel cipher is to use mostly the same software for encryption as for
decryption. This economy is created by XORing the left and right halves,
as you have done. To decrypt in your scheme, you go forward through the
same algorithm as for encryption, so it is a Feistel cipher. What is the
advantage of your scheme? Why is it non-Feistel?
[EMAIL PROTECTED] wrote:
>
> I had been pondering whether or not it was possible, by a suitable choice
> of transformation, to change DES into an equivalent cipher of the form:
>
> XOR subkey
> unkeyed transformation on block
> XOR subkey
> unkeyed transformation on block
> ...
>
> when I finally realized the 'trick' that was needed. The F-function uses
> certain bits from the right half of the block as XORed with two different
> subkey bits. So, to have the extra copy of the bits that is needed,
> subject the plaintext block to the initial permutation - and then subject
> both halves to the expansion permutation, and treat DES as a block cipher
> with a 96-bit block size.
>
> The unkeyed transformation is the XOR of the left half with the f-function
> of the right half; before and after it, XOR the right half with the
> current subkey. Instead of swapping halves, one alternates between two
> unkeyed transformations.
>
> And then I realized that since each transformation only XORs one half with
> a function of the other half, the half that is being XORed need not have
> its correct value; another XOR can happen early or late.
>
> Thus, I realized that it is possible to combine pairs of rounds, so that
> there is only one unkeyed transformation, applied eight times, with nine
> XORs of key material.
>
> This may be made slightly clearer by listing what the nine new 96-bit
> subkeys consist of:
>
> (S2,S1)
> (S2 XOR S4,S1 XOR S3)
> (S4 XOR S6,S3 XOR S5)
> (S6 XOR S8,S5 XOR S7)
> ...
> (S14 XOR S16,S13 XOR S15)
> (S16,S15)
>
> and at the end, one swaps halves, discards duplicate bits, and does IIP.
>
> It may be that this transformation was seen as obvious by people doing
> early analysis of DES, and the reason I hadn't seen it mentioned was
> because it did not help to simplify cryptanalysis.
>
> John Savard
------------------------------
From: Harpy-35 <[EMAIL PROTECTED]>
Subject: Re: [Q. newbie] Authentication/Digital Signatures
Date: Sat, 26 Dec 1998 05:18:47 -1000
Thomas Harte wrote:
>
> Are all authentication/digital signature protocols based on the
> [public-key cryptography-like] concept of private and public
> keys? What I really want to know is whether or not there exist
> protocols for authentication/signing that _cannot_ be turned
> into cryptographic protocols. In other words, are there any
> _pure_ authentication/signature protocols that exist in their
> own right, divorced from any potential cryptographic use?
>
> Thomas.
No. Digital signatures produce unique digital numbers which can be XORed
with plaintext to produce ciphertext.
If you want non-digital signatures, yes.
------------------------------
From: Thomas Harte <[EMAIL PROTECTED]>
Subject: [Q. newbie] Authentication/Digital Signatures
Date: 26 Dec 1998 13:15:37 GMT
Are all authentication/digital signature protocols based on the
[public-key cryptography-like] concept of private and public
keys? What I really want to know is whether or not there exist
protocols for authentication/signing that _cannot_ be turned
into cryptographic protocols. In other words, are there any
_pure_ authentication/signature protocols that exist in their
own right, divorced from any potential cryptographic use?
Thomas.
------------------------------
From: Nathan Kennedy <[EMAIL PROTECTED]>
Subject: Re: [Q. newbie] Authentication/Digital Signatures
Date: Sat, 26 Dec 1998 22:15:36 +0800
Thomas Harte wrote:
>
> Are all authentication/digital signature protocols based on the
> [public-key cryptography-like] concept of private and public
> keys? What I really want to know is whether or not there exist
> protocols for authentication/signing that _cannot_ be turned
> into cryptographic protocols. In other words, are there any
> _pure_ authentication/signature protocols that exist in their
> own right, divorced from any potential cryptographic use?
>
> Thomas.
All authentication/signing requires some sort of secret. If there was
no secret, then there could be no security in the signature because
anybody could sign as you. Like with encryption, using some sort of
key exchange/digital signature mechanism helps with key management a
lot over networks.
You could have a single key authentication mechanism. Basically, tag
a hash of the message plus the secret to the end of the message. The
recipient knows the secret, and hashes the message with the secret.
If it comes out right, it must have come unaltered from someone who
knows the secret. Of course, this has practical limitations, it's no
good for public signatures, because anyone with the secret can
authenticate. This involves no encryption.
Whether or not signing/authentication can be divorced depends on how
divorced you mean. The sticky thing is, when you have the source,
pretty well anything can be used as building blocks for actual
encryption. US government places no restriction on export of
authentication/signature software (I believe) so as long as it is
designed and written only for use as authentication/signing it should
be okay.
But I think hashes could be used to build strong encryption
algorithms. For instance, I suppose you could use the hash function
to make a PRNG for use as a stream cipher, ought to be good for
session keys or use with an IV, but I'm no professional cryptologist
so don't take my word for anything. My point is that there is a fine
line between encryption and no encryption.
Suppose, for instance, I implement Schneier's Twofish algorithm.
Definitely not exportable, right? It's strong encryption. Now
suppose I use it AS A HASH FUNCTION in a mail program, only for error
detection. Is it now exportable? SHA-1 is, why wouldn't
Twofish-the-hash be exportable. If so, it would be trivial to derive
the original encryption function, and as trivial to derive the
corresponding decryption function.
But there's no sense in pointing out examples of the absurdity of
crypto regulation, there's too many more obvious ones to list. Bleh.
Nate
(Gives me another reason to be glad to live in Taiwan. If there's
crypto legislation here, nobody knows. At least, I sure don't.)
------------------------------
From: Harpy-34 <[EMAIL PROTECTED]>
Subject: Re: symmetric encryption with a user-supplied password
Date: Sat, 26 Dec 1998 06:56:43 -1000
denis bider wrote:
>
> I stumbled upon a topic that I have not yet seen discussed: when data is
> being encrypted with a password supplied by the user, for instance by
> 128-bit RC5, how do you create a key that indeed contains 128 bits of
> entropy?
SNIP...
> Can anybody think of a method for raising the entropy of the password
> without straining the user into remembering kilobyte-long streams of random
> data?
>
> --
> denis bider ([EMAIL PROTECTED], [EMAIL PROTECTED])
This is not a perfect answer
to your question, but please consider
the following way to get a password with
between 14 and 16 hexadecimal digits. Many personal
computers have a Calculator accessory with hex capabilities. Try this:
memorize a four digit number (9674). After setting the calculator to
hex notation, raise this to the second power (586c2490). This is
the first half of your 16 digit password. To get the second
eight digits of your password, reverse the memorized
number (4769) and raise this to the second power
(13eb6911). Your password is now complete :
586c249013eb6911. This has 13 bits of
entropy. But each person has the
option of enhancing this method
with some small change which
the person feels she
can remember.
As an
example
of how secure
this is, I used
my credit card PIN
to generate the following
password: 224cc2ca705ca10.
(But I made a simple change
to the method so taking two square
roots will not give the right answer).
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: symmetric encryption with a user-supplied password
Date: Sat, 26 Dec 1998 15:45:54 -0100
denis bider wrote:
>
> when data is
> being encrypted with a password supplied by the user, for instance by
> 128-bit RC5, how do you create a key that indeed contains 128 bits of
> entropy?
>
One possible solution is to remember words instead of letters.
See the diceware page:
http://world.std.com/~reinhold/dir/diceware.html
Even with good passwords the users are a problem. They'll still
still write passwords on tape and stick it under their keyboards,
etc.
The only real solution, if security is critical, is to have the
user carry a floppy disk/smart card/data button around with them
with their key in it.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Re: Transforming DES into a non-Feistel cipher
Date: 26 Dec 98 14:49:02 GMT
Harpy-19 ([EMAIL PROTECTED]) wrote:
: What is the
: advantage of your scheme? Why is it non-Feistel?
It is not meant to be an improvement of DES.
I have checked, though, and this type of transformation of DES _has_ been
done before. Basically, it's much the same as the "48-bit model" of DES
from Basic Methods of Cryptography by Jan C. A. van der Lubbe, although I
go one step further.
Essentially, what I was saying was that one could transform DES so that it
exhibits another structure instead of a Feistel structure; it can be made
to consist of alternate XORs of key material to a whole block, and unkeyed
transforms of the whole block. There happen to be relations between the
subkeys and properties of the transforms such that the Feistel cipher DES
is still being carried out; but in this form, if there are attacks
oriented towards ciphers like SAFER, one can see more plainly how to apply
them to DES.
John Savard
------------------------------
From: Anonymous <[EMAIL PROTECTED]>
Subject: Re: Session keys in Elliptic Curve
Date: 26 Dec 1998 17:46:10 +0100
=====BEGIN PGP SIGNED MESSAGE=====
Mr. Tines wrote:
>> RSA, DH and ElGamal act as enveloping mechanisms in the
>> transport of the session key for a bulk cipher in most
>> PK-cryptosystems. But what about Elliptic Curve? In a
>> cryptosystem using Elliptic Curve as the key exchange
>> algorithm, does it merely act as an enveloping mechanism
>> for the session key, or does it play part in the generation
>> of the session key and thus achieve the exhange of the key?
>
>In the simple case of elliptic curve encryption where
>there is a known generator point P, with secret key x,
>and public key P,P*x then key exchange could be
>accomplished by taking random r and transmitting P*r,
>and using (P*x)*r as the session key - so to that extent
>the EC algorithm participates in the key generation.
So the session key itself is not completely random?
Instead of transmitting a random session key, you transmit
the instructions for reconstructing the session key, namely
the random value x and use the non-random session key for
the bulk cipher itself, correct? Sorry, I want to be sure
about this, I'm not a mathemagician nor a cryptographer.
Isn't this sort of reverse to what RSA etc. use to achieve
key exhange? It is my understanding that these use fully
random session keys for the bulk cipher and transmit
this plain session key without need to reconstruct it
beyond the simple decryption?
With 160 bit elliptic curve key, if you want a 256 bit
session key with enough randomness, how large must the
random x be, and what would be an acceptable method for
generating such value? PRNG augmented with true randomness
and hash that? If so, must the algorithm go up to 256 bits?
>If you need to carry other information along with the
>key (such as algorithm definition as per PGP) in a key
>packet k, then you'd transmit
>
>P*r and ((P*x)*r)^k
>
>which would mean that the session key would not be something
>affected by direct processing through the EC algorithm.
Let's say that we only need to worry about the
transmission of the necessary information to
decrypt the ciphertext of the bulk cipher.
>> If it doesn't, the conventional way to generate session
>> keys is to take output of PRNG and run it through a message
>> digest algorithm, correct? But is there any way to generate
>> 256 bit session keys? Are there any secure hash algorithms
>> that give 256 bit values as output?
>
>HAVAL can generate 256 bit output as does TIGER - or you
>can partition your entropy between two 128-bit generators,
>and build half a key from each.
...and GOST. But what are the reputations of these algorithms?
Are they deemed 'secure enough' for generation of session keys
or generation of hash values for use in digital signatures?
As memory servers, there was a comment somewhere that as of yet
there isn't a sufficient hash algorithm for use with 256 bit
symmetric ciphers, and that maybe Counterpane would be
interested about the subject....?
Entropy between two 128 bit generators? Something like SHA1x?
Wasn't the comment that SHA1x hasn't been shown to be secure
enough? How would this approach work for other algorithms?
BTW, do you have information about elliptic curve keylengths
and their corresponding RSA/DH keylengths? 160 bits equal
something around 1024 bit RSA, but....more?
- --EO
=====BEGIN PGP SIGNATURE=====
Version: PGP 6.0.2
iQEVAwUBNoT2U8gXRmWyooNRAQHAOgf/SEzA73l1IUpDut744elqV9LIfx1C1bnR
1rtYA4QpvMzsUWnvEYiXrMNrzo4Y2sYxG6OsH1iQw4K3087Zr2SgqQUFWVnuuMXl
1qBidAso/Rt1FoBLsLZlXIeeLoQzY73AjycQatrCH0agTTlRMZGwLafcIpilKvAl
wW9+C3mCc1IvMHqQMeWFf+/1aD+RjAsQIzB9IQmhQmVlFErFPo1+XM7T/r628Yu8
4Dqr7+WVihA/uPlbjdpj9wuO/8uWwDPMnDy2kfThaGsg1ivFrKvolrbA0QnUudtn
OD6lDEVRuOlzDYDZlCrKI4ybTuoNi5MzosBVNYzpH39xB5ByB59FmQ==
=+Fwr
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
