Cryptography-Digest Digest #756, Volume #13 Tue, 27 Feb 01 05:13:01 EST
Contents:
Re: Again on key expansion. (Benjamin Goldberg)
Re: CipherText patent still pending (Benjamin Goldberg)
Re: Safe to use DSS key for DH? (David Wagner)
Re: how long can one Arcfour key be used?? ("Scott Fluhrer")
Re: Arcfour in Ada ("Julian Morrison")
Re: how long can one Arcfour key be used?? ("Julian Morrison")
Re: Hash strength question ("Scott Fluhrer")
Re: Help Please !!!!!!!!!!!! (JPeschel)
Re: Rijndael S-box inverse (Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?=)
Help:In RSA, how d is calculated? (David_hopkins)
Help:In RSA, how d is calculated? ("Public " <[EMAIL PROTECTED]>)
Re: Help:In RSA, how d is calculated? ([EMAIL PROTECTED])
Re: Fair(er)play (Jim Gillogly)
Re: CipherText patent still pending (Mok-Kong Shen)
Re: Signature in Merkle-Hellman system (Bo Lin)
Re: How to find a huge prime(1024 bit?) (HiEv)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Again on key expansion.
Date: Tue, 27 Feb 2001 04:20:09 GMT
Cristiano wrote:
>
> This is my question:
> > > I have a password constituted from few characters and I want to
> > > expand it (to at least 128 bits) for use it like session (secret)
> > > key for an algorithm to symmetrical key (e.g. rijndael). How
> > > could I do?
>
> Paul Crowly answer:
> > It's best to apply key stretching: read
> > http://www.counterpane.com/low-entropy.html
>
> In this paper it seems that for expand a key of 64 bits to 128 bits
> are nedeed 2^(128-64) iterations with SHA-1 (do I have understood
> well?).
> With my pc 2^20 itarations takes 9.6 seconds, thus 2^64 iterations
> will takes about 5 millions of years!
Assuming that 2^20 iterations is what is considered practical, then the
most amount of strength you can get from 64 bits of entropy is 84 bits
of strength.
> I think that this is not a practical method!
It is impractical for adding 64 effective bits of strength, sure, but
that's not what it's designed for. The idea is to give a 40 bit key 56
effective bits of strength. This can be done, and is practical -- 2^12
iterations would take .75 seconds on your pc.
In point of fact, I suspect that there IS no practical way to add 64
bits of strength to cryptokey. I would suggest that you just use a
longer key. There *are* easy ways to make long, easily memorizable,
secure, keys.
--
A solution in hand is worth two in the book.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Tue, 27 Feb 2001 04:29:08 GMT
Prichard, Chuck wrote:
[snip]
> The resulting bit pattern that is applied to a message when a
> sophisticated root key is used has a fair amount of integrity, and the
> algorithm itself though simple, cannot be reverse engineered.
Earlier, I said "prove it" to this part of your post. This was a silly
mistake of mine. I should have said, "Who the bleep cares that it can't
be reverse engineered? You've already *given* us the algorithm!"
--
A solution in hand is worth two in the book.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Safe to use DSS key for DH?
Date: 27 Feb 2001 04:30:58 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
lcs Mixmaster Remailer wrote:
>Suppose you have a DSS key, of typical size: prime modulus p of 1024 bits,
>generator g generating a subgroup of size q, where q is 160 bits.
>
>Would it be safe to use this key for DH and/or ElGamal encryption?
>Would you still get ~80 bits of security (based on the modulus size)?
As far as I know, the answer seems to be yes.
But make sure that, whenever you receive a value purported
to be in the subgroup, you always confirm that it is indeed
in the subgroup! Otherwise there are many attacks.
To confirm that y is in a subgroup with odd prime order q,
check that y^q = 1 mod n and that 1<y<n.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: how long can one Arcfour key be used??
Date: Mon, 26 Feb 2001 20:57:29 -0800
Julian Morrison <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Simon Johnson" <[EMAIL PROTECTED]> wrote:
>
> > I think I remember for an average key it is something like a few
> > gigabytes before a bias can be detected in the output. Not sure if this
> > is correct though?
Well, that is correct given current knowledge.
>
> Thanks :-)
>
> Also, does anyone know how this varies with key length and
> number-of-mixes (N in CipherSaber-2)?
Is 'number-of-mixes' the number of passes you do during key setup (with 1
being standard RC4)? If so, then no, that has no effect.
--
poncho
------------------------------
From: "Julian Morrison" <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.ada
Subject: Re: Arcfour in Ada
Date: Tue, 27 Feb 2001 05:07:47 +0000
"Thomas Boschloo" <[EMAIL PROTECTED]> wrote:
> That makes sense. I believe you could perhaps use an escape character to
> identify the end of a string. Like (and I have to dig deep into my
> memory now) when you send a bit string, you could say that '000' marks
> the end of your bit string. If you need to actualy send '000' you pad it
> like '0010' or something like that. I am a bit rusty, have to look it up
> in my old study books.
Problems with that: you have to scan and escape, scan and de-escape every
byte or byte-pair. Also over any nontrivial length of binary data, you are
likely to need many escaped characters. Worst case, this can double your
packet length. Contrast this with say a 64 bit "expect thus many bytes"
header.
Either way tho, you need to waste some overheads on that.
> [...] I don't know much about implementing TCP. I
> do know that the freedom network stopped using fixed sized packages in
> version 2.1 or something, because it took up too much bandwidth.
Yeah. Likely because most network traffic is small, so padding up to a
fixed packet size mostly wastes space. The idea of padding is to make it
impossible to use packet sizes to do traffic analysis.
The way I'm thinking of doing that for my system, is:
- each machine has a queue of multiple "inboxes", and one "outbox".
- there is one inbox per intended recipient
- inboxes are created on a first come first served basis
- any packets recieved for a recipient with an existing inbox, go into
that existing inbox
- the sender part moves the first inbox off the queue and sends it all,
then discards it and moves on to the next, etc
- to send packets, they are crammed together but then padded at
then end to an integer number of fixed size blocks.
Then the bandwith wastage is only at most a block minus one byte. Of
course in reality the algorithm will be a tad more complex, for example
having a maximum size for inboxes to prevent popular recipients typing up
the outbound line.
This relies on the assumption that in most cases, although traffic is
small, it's going repetitively to the same recipient.
> I seem to remember that they also use UDP for something but I am
> confusing myself now. The good thing about UDP is that you don't have to
> set up a connection to send data. It doesn't have to point back to you
> (which is good if you want to be anonymous).
Thanks, you gave me a useful idea there - UDP outbound can have a forged
"from" IP. Although I don't know how useful it will be in this system;
each relay needs to send an "ack" back upstream after sending its
messages. But it might be useful; I'll give it some thought.
> Well, who do I think I am :-) I'm sure you already know all you need to
> know and more ;-)
Heh, I'm much of a newbie too. I built my Arcfour code from the
ciphersaber cookbooks online; I'm no mathematician. Just a coder with an
algorithm and some test data to validate against.
------------------------------
From: "Julian Morrison" <[EMAIL PROTECTED]>
Subject: Re: how long can one Arcfour key be used??
Date: Tue, 27 Feb 2001 05:16:48 +0000
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
>> Also, does anyone know how this varies with key length and
>> number-of-mixes (N in CipherSaber-2)?
> Is 'number-of-mixes' the number of passes you do during key setup (with
> 1 being standard RC4)?
Yes.
> If so, then no, that has no effect.
Ok. How about key length? One of my intended algorithms will use throwaway
from-scratch DH to setup a key, but creating DH primes for a full length
256 byte RC4 key would take several minutes a pop, way too slow. (I'm
doing it this way so as to have "forward security" - once the transaction
is over, there should be no way to decrypt it from wiretap records and a
siezed machine.)
For example, CipherSaber suggests a 62 byte key + IV; for how long could
that be used?
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Hash strength question
Date: Mon, 26 Feb 2001 21:11:41 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> This might or might not sound like a silly question, but:
>
> Suppose we have a hardware chip that can create a secure hash, which can
> process data at X bytes per second.
>
> Suppose we have a stream of data coming in at 2X bytes per second.
>
> Does it weaken the security to take two hashing chips, send alternate
> bytes of the stream to each chip, and when done, hash the two hashes
> together?
>
> eg:
> stream = "abcdefghijkl"
> hash = H( H("acegik") || H("bdfhjl") )
>
> Is this hash more or less secure than doing H("abcdefghijkl")?
>
> And if it is, does this extend to more than two hashes?
>
> Also, can we use the H("acegik") XOR H("bdfhjl")?
Lets think about this: a hash is considered secure if it is computationally
impractical to create two items that hash to the same value (oh, and
preimage resistance, which can be analyzed similarly). Now, in your first
example, if you do have a nontrival collision for your hash function at
values x, y with interleaved values x = xXxXxXxXxX and y = yYyYyYy, then you
have
x != y
hash(x) = hash(y)
or
H(H(xxxxxx) || H(XXXXX)) = H(H(yyyy) || H(YYY))
Then, you have found a nontrivial colision in one of following pairs:
H(xxxxx) || H(XXXXX), H(yyyy) || H(YYY)
H(xxxxxx), H(yyyy)
H(XXXXX), H(YYY)
(proof left as exercise for the reader) and so the if we find a weakness in
hash, we must also find a weakness in the underlying H function. Hence hash
is at least as secure as H. And, yes, it extends in the obvious way to
multiple hashes.
On the other hand, the XOR method is trivially insecure. For example, it
hashes the strings "01" and "10" into the same value.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 27 Feb 2001 06:07:58 GMT
Subject: Re: Help Please !!!!!!!!!!!!
PADDOCK [EMAIL PROTECTED] writes:
>the following is a list of unix crypt passwords
>
>have broken 15 of them
>nbr:NgrdOQvGJxApM:Brian Randell
(from a partial UNIX pwd.lst)
Does this list include the 15 you've broken?
I've retrieved 9 pwds using John (in its deafult mode,)
no rules, and a mid-sized 1/4 Gig wordlist. Took
around 16 minutes on my P-1.4Ghz machine.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Panu =?iso-8859-1?Q?H=E4m=E4l=E4inen?= <[EMAIL PROTECTED]>
Subject: Re: Rijndael S-box inverse
Date: Tue, 27 Feb 2001 08:13:33 +0200
Manuel Pancorbo wrote:
> BTW, are you parent of Riitta H�m�l�inen?
No, I'm not. The name is quite common in Finland.
-- Panu
------------------------------
From: David_hopkins <[EMAIL PROTECTED]>
Subject: Help:In RSA, how d is calculated?
Date: Tue, 27 Feb 2001 05:22:18 +0000
N = P x Q = 37x 13= 481
PHI = (P-1)(Q-1) = 432
The public exponent E will be generated by the computer
so that the greater common divisor of E and PHI is 1.
In other words, E is relatively prime with PHI.
E = 5
N and E are your public keys. Your private key (D) is the
inverse of E modulo PHI.
By using extended Euclidian algorithm, the private key, D, is 173
!!! how d is calculate?
Thank you.
_______________________________________________
Submitted via WebNewsReader of http://www.interbulletin.com
------------------------------
Date: Tue, 27 Feb 2001 00:25:08 -0600
From: "Public <Anonymous_Account>" <[EMAIL PROTECTED]>
Subject: Help:In RSA, how d is calculated?
N = P x Q = 37x 13= 481
PHI = (P-1)(Q-1) = 432
The public exponent E will be generated by the computer
so that the greater common divisor of E and PHI is 1.
In other words, E is relatively prime with PHI.
E = 5
N and E are your public keys. Your private key (D) is the
inverse of E modulo PHI.
By using extended Euclidian algorithm, the private key, D, is 173
how d is calculate?
Thank you.
---
This message did not originate from the Sender address above.
It was posted with the use of anonymizing software at
http://anon.xg.nu
---
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Help:In RSA, how d is calculated?
Date: 27 Feb 2001 01:34:05 -0500
David_hopkins <[EMAIL PROTECTED]> wrote:
> N = P x Q = 37x 13= 481
> PHI = (P-1)(Q-1) = 432
> The public exponent E will be generated by the computer
> so that the greater common divisor of E and PHI is 1.
> In other words, E is relatively prime with PHI.
> E = 5
> N and E are your public keys. Your private key (D) is the
> inverse of E modulo PHI.
> By using extended Euclidian algorithm, the private key, D, is 173
> !!! how d is calculate?
There are various ways to programme the extended Euclidean algorithm.
The easiest way for me (at least) to remember it is that it is the
penultimate approximant in the continued fraction for PHI/E
(that is, if the approximant before the last of PHI/E is M/N, then
M*E-PHI*N=+/-1. If it is +1, then ME=1 mod PHI and d=M.
If it is -1, then take d=PHI-M=-M mod phi and d*e=1 mod phi again)
In the example given:
432/5 (PHI/E) is:
86 + 1/(2 + 1/(2))
(a continued fration is:
a+1/(b+1/(c+1/(d+1/(e...)))) where
a,b,c,d,e ... are positive integers.
There are some extensions where a,b,c,d... don't have to be integers,
but in working with rationals, we use the usual definition where
they are. Any positive rational number has a continued fraction
which just has finitely many steps until you reach the exact value
of the fraction/rational number, itself)
The first approximant to PHI/E is 86.
The second is 86+1/2=173/2
The third (and last) is 86+(1/(2+1/2))=432/5=PHI/E)
(this gives the original number)
The one before the last is 173/2 (M=173, N=2)
E*M-PHI*N = +/-1
(5*173 - 2*432 will be +/-1)
which is it? It happens to be +1 so:
5*173=1 mod 432
(if it had come out -1, one would have used d=432-173, but
that is wrong in this case ... it depends upon whether the
penultimate approximant appears after an even or odd
number of steps)
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Fair(er)play
Date: Tue, 27 Feb 2001 08:17:33 +0000
JPeschel wrote:
>
> To my web site, I've just added Gunnar Andersson's new
> release of Fairplay, a Playfair hill-climber, dated 2/18/2001.
...
> He has included in this release six ciphertext examples,
> two of which give Fairplay trouble:
>
> ecoo1999.txt An example from www.ecoo.org/sigcs/finals/fin1994p4.html.
> hg149.txt Taken from Helen Gaines' book "Cryptanalysis".
> hg150.txt - " " -
> hg153.txt - " " -
> nova.txt From the Nova competition.
> stage6.txt Stage 6 of the cipher challenge in "The Codebook"
> by Simon Singh.
>
> My P-1.4 cracks four of ciphertexts in roughly this order:
> stage6.txt, hg153, hg150, and nova.txt.
>
> It has trouble with hg149 and ecoo1999. I suspect the
> hg149 ciphertext is too short for Fairplay to crack. Ecoo1999,
> on the hand, includes plenty of ciphertext, but the plaintext
> has an high occurrence of an unusual digram.
>
> Let me know if you have better luck than I did cracking
> ecoo1999 and hg149, or if you have suggestions about cracking
> them.
I've found it useful in my hillclimber to optionally allow it to try
hillclimbing to a key shorter than the entire 25-letter key frame.
My first try at hg149 was telling it to attempt to optimize a key no
longer than 8 letters using the straightforward key path (i.e. by
rows), much like Alf Monge's assumption in his famous short solution
reprinted in one of the Friedman books from Aegean Park Press.
Additionally I can require a coherent key: that is, I include the
key as part of the plaintext that's being scored, allowing for a little
more help in short cryptograms. Using both of these heuristics I got
a solution with the first attempt in just a few minutes. A proper name
in the plaintext is misspelled -- it turns out to be a couple of blocks
from my late parents' home in San Pedro.
A technique I sometimes use on resistant or long cryptograms (like
Kryptos, for example) is to take a small piece of it and try to solve
that. For ecoo1999 after some boring failures I tried just the last
line and tried solving it with progressively longer keys. After about
half an hour the right one turned up at length 9. This heuristic can
be useful because it cuts down the decryption time.
--
Jim Gillogly
Hevensday, 7 Rethe S.R. 2001, 08:07
12.19.8.0.3, 3 Akbal 6 Kayab, Third Lord of Night
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: CipherText patent still pending
Date: Tue, 27 Feb 2001 09:48:34 +0100
"Prichard, Chuck" wrote:
>
> The idea to use a key attibute to articulate rotation of a somehow
> modified key has been implemented and demonstrated with no response from
> this newgroup by someone who has claimed to have previously used it. I
You must have posted it quite a time back. If that's indeed
the case, you have to repeat with a conscise description if
you want discussions. If that post was very recent, a
reference is needed.
M. K. Shen
------------------------------
From: Bo Lin <[EMAIL PROTECTED]>
Subject: Re: Signature in Merkle-Hellman system
Date: Tue, 27 Feb 2001 08:58:37 +0000
See D. E. Denning, "Cryptography and Data Security", 1982, pp.122 - 125.
mklai wrote:
>
> This may be a novice question. And it may not of practical interest because
> the Merkle-Hellman knapsack cryptosystem has long been broken.
>
> The title of Merkle and Hellman's paper is "Hiding Information and
> *Signatures* in Trapdoor Knapsacks." But I read from a book that the
> Merkle-Hellman knapsack cryptosystem cannot be used for authentication.
> "The reason is that the enciphering transformation does not map the entire
> message space back onto itself; thus, it is not possible to take an
> arbitrary message and sign it by applying the deciphering transformation."
> So, what kind of "signatures" was the Merkle-Hellman paper talking about?
>
> Thanks.
------------------------------
From: HiEv <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,sci.math
Subject: Re: How to find a huge prime(1024 bit?)
Date: Tue, 27 Feb 2001 09:25:49 GMT
Thomas Boschloo wrote:
>
[snip]
> I still am not smart enough to prove there are places where there are a
> lot of prime numbers after one another, but I hope I have shown that
> there are also places where there are large gaps between them. Maybe
> more than N/ln(N).
[snip]
The most "consecutive" primes (i.e.. N and N+2) you can have for N>5 is
two, and they will always end with 1 and 3, 7 and 9, or 9 and 1. The
reason why is that all that end in 5 are multiples of 5, and in all
other cases N+4 must be a multiple of 3.
For example: (*N* = Prime, -N- = multiple of 3)
*11*, -12-, *13*, 14, -15-
*17*, -18-, *19*, 20, -21-
*29*, -30-, *31*, 32, -33-
Thus all twin primes must bracket a multiple of 3.
This tells you that if you have just found a twin prime (two
"consecutive" primes) then you can skip the next odd number. Heck, you
can skip every third odd number (starting with 9) because they will all
be multiples of three.
------------------------------
** 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
******************************
