Cryptography-Digest Digest #665, Volume #12 Tue, 12 Sep 00 20:13:00 EDT
Contents:
Re: rc4 -- repetition length ([EMAIL PROTECTED])
Re: RSA?? (Simon Johnson)
Re: Need Tiger hash results for sample test data (Jim Gillogly)
Re: Weaknesses in this algorithm? (John Myre)
Re: rc4 -- repetition length ([EMAIL PROTECTED])
Re: search for better serpent sboxes (Tom St Denis)
Re: nice simple function (Tom St Denis)
Re: Need Tiger hash results for sample test data (John Myre)
Re: RSA public exponent (Bryan Olson)
Can anyone decrypt this? ("medievalist")
Re: Getting Started, advice needed (FAQs , yes I read them) ("Paul Pires")
Re: [Q] Design criteria for sboxes in Tiger/192 ? (Tom St Denis)
Re: Intel's 1.13 MHZ chip (John Savard)
Re: SV: Intel's 1.13 MHZ chip ("Abyssmal_Unit_#3")
Re: For the Gurus ("root@localhost " <[EMAIL PROTECTED]>)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: rc4 -- repetition length
Date: Tue, 12 Sep 2000 21:58:52 GMT
There are cycles in 3-bit rc4 that are of length 2*8. That's shorter
than the cycles of size 7*8 that are avoided by avoiding i=j, m[i]=1.
I'm looking at 4-bit rc4 now, but its state is too big to search, so I
probably won't find anything.
There are probably very short cycles in the real (8-bit) rc4 that aren't
avoided too. They should contain a completely negligible fraction of
all possible states, but they probably exist. There is certainly no
guarantee in rc4 that cycles will be long.
The states with i=0 lying on short cycles in 3-bit rc4 are:
cycle length: 2 i = 0, j = 0
m = 4 6 2 7 0 5 1 3
cycle length: 2 i = 0, j = 0
m = 4 6 3 7 0 5 1 2
cycle length: 2 i = 0, j = 0
m = 6 7 4 5 1 2 0 3
cycle length: 2 i = 0, j = 0
m = 6 7 4 5 1 3 0 2
cycle length: 2 i = 0, j = 0
m = 6 7 5 4 1 3 0 2
cycle length: 2 i = 0, j = 0
m = 7 1 0 3 5 6 2 4
cycle length: 2 i = 0, j = 0
m = 7 1 0 4 2 6 3 5
cycle length: 2 i = 0, j = 0
m = 7 1 0 4 3 6 2 5
cycle length: 2 i = 0, j = 2
m = 1 7 4 2 0 3 5 6
cycle length: 2 i = 0, j = 2
m = 1 7 5 2 0 4 3 6
cycle length: 2 i = 0, j = 2
m = 1 7 5 3 0 4 2 6
cycle length: 2 i = 0, j = 2
m = 7 4 1 0 3 5 6 2
cycle length: 2 i = 0, j = 2
m = 7 5 1 0 4 2 6 3
cycle length: 2 i = 0, j = 2
m = 7 5 1 0 4 3 6 2
cycle length: 2 i = 0, j = 3
m = 4 5 1 7 6 2 0 3
cycle length: 2 i = 0, j = 3
m = 4 5 1 7 6 3 0 2
cycle length: 2 i = 0, j = 3
m = 5 4 1 7 6 2 0 3
cycle length: 2 i = 0, j = 3
m = 6 2 7 4 5 1 3 0
cycle length: 2 i = 0, j = 3
m = 6 2 7 5 4 1 3 0
cycle length: 2 i = 0, j = 3
m = 6 3 7 4 5 1 2 0
cycle length: 2 i = 0, j = 5
m = 3 5 6 2 7 0 4 1
cycle length: 2 i = 0, j = 5
m = 4 2 6 3 7 0 5 1
cycle length: 2 i = 0, j = 5
m = 4 3 6 2 7 0 5 1
cycle length: 2 i = 0, j = 5
m = 7 4 5 1 2 6 3 0
cycle length: 2 i = 0, j = 5
m = 7 4 5 1 3 6 2 0
cycle length: 2 i = 0, j = 5
m = 7 5 4 1 3 6 2 0
cycle length: 2 i = 0, j = 6
m = 0 3 5 6 2 7 1 4
cycle length: 2 i = 0, j = 6
m = 0 4 2 6 3 7 1 5
cycle length: 2 i = 0, j = 6
m = 0 4 3 6 2 7 1 5
cycle length: 2 i = 0, j = 6
m = 1 0 3 5 6 2 7 4
cycle length: 2 i = 0, j = 6
m = 1 0 4 2 6 3 7 5
cycle length: 2 i = 0, j = 6
m = 1 0 4 3 6 2 7 5
cycle length: 2 i = 0, j = 6
m = 5 1 7 6 2 0 4 3
cycle length: 2 i = 0, j = 6
m = 5 1 7 6 3 0 4 2
cycle length: 2 i = 0, j = 7
m = 4 1 7 6 2 0 3 5
cycle length: 2 i = 0, j = 7
m = 5 6 2 7 0 4 1 3
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: RSA??
Date: Tue, 12 Sep 2000 22:03:54 GMT
In article <8pd7c1$ck6$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <eIju5.248105$[EMAIL PROTECTED]>,
> "Big Boy Barry" <[EMAIL PROTECTED]> wrote:
> > Is RSA encryption unsecure? I know nothing is 100% secure... but I
> would
> > like your opinion on RSA?
>
> Um, no to the best of my knowledge when used correctly RSA is still
> considered secure.
>
> Tom
>
RSA security lies in the assumption that is as hard to break as it is
to factoring the modulo. This assumption has considerable weight so,
provided you're primes are big enough its reasonable to say its secure.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Need Tiger hash results for sample test data
Date: Tue, 12 Sep 2000 22:14:24 +0000
[EMAIL PROTECTED] wrote:
> Well, for starters, lets consider an example with our old friend md5. If
> I want to create an md5 hash on the string 'abc', I could simply run:
> 'md5 -sabc', which yields:MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
> This is not, however, what I would get if I created a file (abc.txt),
> containing the string 'abc' and then ran md5 against it as: 'md5
> abc.txt' or 'cat abc.txt | md5'. Both of these would yield:
> MD5 (abc) = 0bee89b07a248e27c83fc3d5951213c1
No, I get your original hash "90015...". You must have a newline
at the end of your file. Works fine here, assuming an editor that
doesn't try to outsmart you.
To verify it for yourself without the editor getting in your way,
write a 1-line program that prints "abc" and send it to a file.
--
Jim Gillogly
Hevensday, 21 Halimath S.R. 2000, 22:10
12.19.7.9.15, 4 Men 18 Mol, Sixth Lord of Night
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Weaknesses in this algorithm?
Date: Tue, 12 Sep 2000 16:10:55 -0600
ArchimeDES wrote:
> On 11 Sep 2000 16:32:11 GMT, [EMAIL PROTECTED] (Mark Wooding) wrote:
<snip>
> > P \xor K, R \xor RC4(K), M \xor R
> Hmmm, no:
> we send P \xor K, RC4(K,R), M \xor R.
<snip>
Would you like to reconsider differentiating "R \xor RC4(K)"
and "RC4(K,R)"? Have you confused RC4 with something else?
JM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: rc4 -- repetition length
Date: Tue, 12 Sep 2000 22:13:12 GMT
In article <8pm8ug$jfk$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> There are cycles in 3-bit rc4 that are of length 2*8. That's shorter
> than the cycles of size 7*8 that are avoided by avoiding i=j, m[i]=1.
Oops. 3*8, not 2*8.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: search for better serpent sboxes
Date: Tue, 12 Sep 2000 22:26:03 GMT
In article <8pm8ia$j3a$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> In article <8pm7vp$ibl$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > With my sboxgen program [1] I am searching for 4x4 sboxes that have
a
> > LPmax of 4, a DPmax of 4, fulfill SAC and BIC (order 3).
> >
> > Currently on my comp I get about 250,000 sboxes tested per second,
but
> > if we had 1000 comps searching that would be an awesome figure. On
my
> > website
> >
> > [1] www.geocities.com/tomstdenis/
> >
> > I have a copy of sboxgen in source form, but I modified it at home
to
> > also give a rate output display while it's searching. If anyone
> want's
> > an executable form of the program I am more then happy to share it.
> >
> > I could even embed the parameters so no setup is required!
> >
> > These sboxes could be used in serpent as replacement functions...
> >
> > Tom
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
> >
> Ask distributed.net and see if they'll let you code a thingy for this
> task! If not, clone it :)
I am not popular enough to be deserving of their time ... they will
just brush me off.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: nice simple function
Date: Tue, 12 Sep 2000 22:27:13 GMT
In article <8pm85t$iev$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> Right, what is linearness? - Clearly its a measure of the vunrability
> to attack by linear cryptanaylsis. So the next question is what is
> linear cryptanylsis? I don't think this question has ever been
answered
> properly while i've been posting/reading. :)
>
> Thanxs :)
F(x) = a.x + b is only linearly solvable with TWO pairs of
inputs/outputs. If I tell you F(3) = 14, what was my 'a,b'? you can't
tell from random...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Need Tiger hash results for sample test data
Date: Tue, 12 Sep 2000 16:32:10 -0600
Jim Gillogly wrote:
<snip>
> To verify it for yourself without the editor getting in your way,
> write a 1-line program that prints "abc" and send it to a file.
Assuming he doesn't use "puts()" ...
JM
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: RSA public exponent
Date: Tue, 12 Sep 2000 22:40:44 GMT
Mark Wooding wrote:
> The algorithm which recovers the factors needs only
> knowledge of a multiple of \lambda(n). It works like
> this:
For those who want to see it action, here is working
Python code for the algorithm.
The Python language is elegant, portable and free. It has
long integers built-in, and is an excellent language for
cryptologic exploration. For the most popular platforms
there are free binary distributions that install cleanly.
See: http://www.python.org.
The vertical bars in the leftmost column are not part of the
Python code. They're there to prevent the defective
Dejanews posting form from destroying the line spacing.
|
| import whrandom
|
| def gcd(x, y):
| """Return the greatest common divisor of x and y.
| """
| while x>0:
| x, y = y%x, x
| return y
|
|
| def factor_using_lambda(n, lam):
| """Given a composite n and lambda (or any multiple
| of lambda), return a factor.
| """
|
| # Divide factors of two out of lam.
| s = lam
| while s & 1 == 0:
| s = s >> 1
|
| # Repeat until we find a factor.
| for i in range(100):
|
| # Choose a random base
| base = long(whrandom.randint(2, 0x7FFFFF))
|
| # Python has built-in modular exponentiation
| a = pow(base, s, n)
|
| if a == 1:
| # Not useful, try another base
| continue
|
| assert pow(a, lam/s, n) == 1, "Bad lambda"
|
| # Square until we get plus or minus one
| while a != 1 and a != n-1:
| b = a
| a = a * a % n
|
| # Plus one given non-trival square root.
| if a == 1:
| return gcd(n, b + 1)
|
| # Minus one is not useful; loop again.
|
| # Failure if we get here.
| assert(0), "This should never happen"
|
|
| # Example:
| p = 822840473723171237451836278714786182824974931L
| q = 973651875618689711856198257834683029454567L
| n = p * q
| totient = (p-1) * (q-1)
| factor = factor_using_lambda(n, totient)
| print p
| print q
| print factor
| assert factor == p or factor == q
|
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "medievalist" <[EMAIL PROTECTED]>
Crossposted-To: comp.mail.pegasus-mail.ms-windows
Subject: Can anyone decrypt this?
Date: Tue, 12 Sep 2000 23:03:59 GMT
The widely used Pegasus Email for Windows software (by David Harris of New
Zealand) requires storage of user IMAP and POP passwords. These passwords
are never displayed or stored in clear text, probably as a defense against
"shoulder surfing".
The POP password encryption is trivial and has been cracked. The crack is
useful to system administrators who wish to set up large numbers of accounts
for relatively clueless users - they can automatically populate the pegasus
.ini file when *nix accounts are generated, and during user password
changes, by use of scripts and samba. The .ini file is then protected with
the standard *nix protection mechanisms (obviously samba's use of CIFS makes
that harder, but it is doable in a well-designed and appropriately monitored
net).
The IMAP password encryption has not been cracked yet. Pegasus Support do
not reply to email on the subject (and David Harris does not allow
inspection of his algorithms or source code). Sysadmins who wish to convert
to IMAP are stuck with POP3 if they do not have the resources for
large-scale user training. This is commonplace; Pegasus is sufficiently
user-friendly that it is an excellent choice to distribute to end-users who
are very nearly computer-illiterate. Unfortunately this same body of users
typically are the worst victims of POP3; they never delete their Email and
it grows to clutter their systems until they grind to a halt.
Here is a Pegasus IMAP.PM file. The password to testly is a long string
of "a"s, the remaining passwords are identical to the userIDs (so, for
example, account penguin has password penguin).
Profile: "testly",28672,"test",143,"test",5441,"=W{rJb5JK.*+Q_=E7Q>dx;&LsVf
/XA<(S2}7R3:NPrIS*","",0,30
Profile: "Miguel de
Icaza",28672,"MdImail.Gnome.Org",143,"miguel",21577,"V'xN+f","mybox",0,30
Profile: "Alan
Cox",28672,"ACbox.linux.org",143,"Alan",5881,"_O>D","myboxes",0,30
Profile: "Linus
Torvalds",28672,"mail.transmeta.com",143,"penguin",25240,"VM0#DhR","tuxedo/j
unction",0,30
Fields are:
a label, an array of option flags that control email handling, IMAP host,
IMAP port, IMAP userID, crypto key?, encrypted password?, another flag, time
interval between IMAP mail checks
Pegasus Email v3.12c (earlier versions do not include IMAP) is freeware
and available for download at http://www.pegasus.usa.com/downloads.htm as
well as most large public FTP sites. IMAP profiles are entered through the
"tools" menu, and all IMAP passwords are recalculated each time the IMAP.PM
file is written.
It is my hope that someone more cryptologically inclined than myself will
find this interesting enough to crack, so that I can write some automated
password maintenance tools for this very useful and friendly mailer.
I expect to be roundly flamed, both for supplying Email to the clueless
(hey, they have other useful skills that make them worth communicating with,
and communication is the first step towards the clue train) and for
suggesting that there is a legitimate need to crack the code. Don't worry,
I have my asbestos hip-boots on (fibrefrax is for sissies) so I imagine I'll
survive :^}.
--Charlie
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Getting Started, advice needed (FAQs , yes I read them)
Date: Tue, 12 Sep 2000 16:30:47 -0700
Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
news:8pjugo$l7q$[EMAIL PROTECTED]...
>
> Paul Pires <[EMAIL PROTECTED]> wrote in message
> news:cI%u5.61866$[EMAIL PROTECTED]...
> >
> > Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
> > news:8phpk5$plr$[EMAIL PROTECTED]...
> > >
> > > Paul Pires <[EMAIL PROTECTED]> wrote in message
> > > news:U_Yu5.60123$[EMAIL PROTECTED]...
> > > > Why would anyone brute force the key. It seems to me that if
> > > > you can be made to encrypt some known material at the
> > > > beginning of a file, I get your key using only a pencil and
> > > > paper.
> > > >
> > > > first tempKey = theKey;
> > > >
> > > > > temp1 = data[counter] + tempKey;
> > > > > temp1 = ((temp1 << 19) | (temp1 >>13)) - 26087;
> > > > > temp1 = ((temp1 << 23) | (temp1 >> 9));
> > > > > tempData[counter] = temp1;
> > > > > tempKey = tempKey + temp1 - 26087;
> > > >
> > > > Let's refrase the first cycle:
> > > >
> > > > temp1 = plaintext + the honest to god key;
> > > > temp2 = ((temp1 << 19) | (temp1 >>13)) - 26087;
> > > > temp3 = ((temp1 << 23) | (temp1 >> 9));
> > > Actually, this should be:
> > > temp3 = ((temp2 << 23) | (temp2 >> 9));
> > >
> > > > ciphertext= temp3;
> > > > tempKey = tempKey + temp1 - 26087;
> > > Actually, this should be:
> > > tempKey = tempKey + temp3 - 26087;
> > > Neither of these affect your attack materially...
> >
> > Sorry for the typo's. I finally found an easy one to respond to
> > and was rushing like mad to post it before the real guns saw it :-)
>
> No problem -- I know the feeling. "I gotta get this break out before Wagner
> sees the post, and stomps the system flat..."
>
> > > Actually, this attack can be strengthened somewhat, in that it can be
> > > applied to any block (and, it relies on a known plaintext block, rather
> than
> > > a chosen one as you appeared to have implied). Suppose you know/guess
> the
> > > value of plaintext block 10. Then, you use the above attack to derive
> the
> > > value of tempKey at the start of the encryption of block 10. Then,
> looking
> > > at the last two steps of the iteration for block 9:
> > >
> [snip]
> >
> > Yep, that works too.
>
> Actually, thinking about the system some more (yes, I don't have a life...
> why do you ask?), the system is essentially:
>
> C = F( P+K )
> K += C + Const
>
> where:
> P is the plaintext block
> C is the ciphertext block
> K is hidden state, initialized to be the key
> Const is -26087
> F is an unkeyed invertible 32 bit->32 bit function
> Finv is the inverse of F
> All addition/subtraction is done mod 2**32
>
> then,
>
> Finv(C) - P = K
>
> Then, if we have two adjacent ciphertext blocks C1, C2, then
>
> Finv(C1) - P1 = K1
> Finv(C2) - P2 = K2
> K2 = K1 + C1 + Const
Be gentle, If I go FUBAR here, please forgive.
Doesn't this also mean that K2-K1 = C1 + Const ?
Wouldn't this mean that the diference between adjacent round
keys is defined entirely by the first ciphertext? So if C1 is
(2^32) - Const , Then C1 + Const = 0, and K2 = K1 ?
Wierd property. I wonder if you could craft a chosen ciphertext
hack on it? Some way of fooling the guy into handling two
adjacent blocks with the same working key.
What does that get me? I think I just lost myself.
Paul
>
> or
>
> P2 - P1 = Finv(C2) - Finv(C1) - C1 - Const
>
> Everything on the right side is known to the attacker, and so he can deduce
> the arithmetic differences between any two blocks. Depending on the
> characteristics of the plaintext (eg. if there is a checksum of all the
> blocks at the end of the plaintext), this may make recovering it real
> easy...
>
> --
> poncho
>
>
>
>
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: [Q] Design criteria for sboxes in Tiger/192 ?
Date: Tue, 12 Sep 2000 23:48:33 GMT
In article <[EMAIL PROTECTED]>,
Runu Knips <[EMAIL PROTECTED]> wrote:
> Eli Biham has designed a hash function, Tiger/192
> (see http://www.cs.technion.ac.il/~biham/ and
> http://www.cs.technion.ac.il/~biham/Reports/Tiger/).
> It also has a nice paper which describes almost
> everything except the design of the Sboxes. Does
> anyone have any information (or an idea) how they
> have been constructed ?
In [1] we find the 7 stated requirements
1. All the entries of all the sboxes should be distinct. Moreover no
two entries should have more then three equal bytes.
2. Each byte column is a permutation of all 256 possible byte values.
3. The column of all sboxes should be as different as possible and
have long cycles.
4. No two differences of sbox entries Si(t1)^Si(t2) and Sj(t3)^Sj(t4)
should have more then four equal bytes.
5. The speed of generation should not be too slow, in order to make
them on the fly.
6. [cited] Chosen to reduce linear/differential properties and to make
the characteristics less alike
7. The randomizing parameter is easy to remember.
---
[1] Generation of the S Boxes of Tiger
Personally I would use 8 very good 8x8 sboxes and a MDS matrix :-)
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Intel's 1.13 MHZ chip
Date: Tue, 12 Sep 2000 23:51:53 GMT
On Tue, 12 Sep 2000 10:15:28 -0600, Jerry Coffin <[EMAIL PROTECTED]>
wrote, in part:
>Seymour Cray's last machines were running at a 1 GHz clock speed
>around 10 years ago now. OTOH, the earlier comment about the
>military having used this level of technology for that long appears
>likely to be more or less erroneous -- essentially all the orders for
>these machines were cancelled, so only three were ever built and
>unless memory deceives me, none of those ever went to the military,
>NSA or anything similar. One stayed at the Cray plant here in
>Colorado Springs. One went to the University of Colorado. Offhand I
>don't remember exactly where the third went, but it seems like it was
>to a university as well. FWIW, at one time the government HAD
>ordered them, but they ended up getting so far behind schedule that
>the orders got cancelled.
If the government did not express interest once Cray had machines
ready to ship, one is tempted to speculate that the NSA, at least,
might have had machines of similar speed from internal production: it
is difficult to believe that their appetite for processing power was
anything other than insatiable at that time as at any other.
But this is an interesting historical tidbit.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Abyssmal_Unit_#3" <[EMAIL PROTECTED]>
Subject: Re: SV: Intel's 1.13 MHZ chip
Date: Tue, 12 Sep 2000 20:01:04 -0400
yocto !
how about infinto! or statico!
err umm, just kidding, sorry! ;-))
--
best regards,
hapticz
>X(sign here)____________________________________________<
S. T. L. wrote in message <[EMAIL PROTECTED]>...
|/*T - tera p - pico 1 000 000 000 000*/
|
|Aw, come on, you forgot peta and femto, exa and atto, not to mention zotta and
|zocto, yotta and yocto. :-P
|
|-*---*-------
|S.T.L. My Quotes Page: http://quote.cjb.net
|Book Reviews Page: http://sciencebook.cjb.net
|Turbo-nifty interlaced interpolated PNG demo: http://interpng.cjb.net
|Coming soon: pngacc, a PNG optimizer!
|Long live pngcrush!
------------------------------
From: "root@localhost <spamthis>" <[EMAIL PROTECTED]>
Subject: Re: For the Gurus
Date: Tue, 12 Sep 2000 19:56:50 -0400
Is my question too trivial?
--
If children don't know why their grandparents did what they
did, shall those children know what is worth preserving and what
should change?
http://www.cryptography.org/getpgp.htm
------------------------------
** 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
******************************
