Cryptography-Digest Digest #596, Volume #10 Sat, 20 Nov 99 07:13:02 EST
Contents:
Re: bits of diffiehellman private key (David Hopwood)
Re: What part of 'You need the key to know' don't you people get? (Tom)
Re: What part of 'You need the key to know' don't you people get? (Boris Kazak)
Re: AES cyphers leak information like sieves (John Savard)
Re: Apparently, Hushmail does work (David Hopwood)
Re: Apparently, Hushmail does work (David Hopwood)
Re: Distribution of intelligence in the crypto field (The Walters)
Re: Distribution of intelligence in the crypto field (M Okra)
Re: A Random Key Cipher Machine (Mark Adkins)
----------------------------------------------------------------------------
Date: Sat, 20 Nov 1999 04:57:19 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: bits of diffiehellman private key
=====BEGIN PGP SIGNED MESSAGE=====
In message <814gea$b07$[EMAIL PROTECTED]>
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Let's say you have a random 1024 bit private exponent, and only 128 of
> those bits are random [not clumped together]. Let's say for any random
> key you could tell which bits were not random but their position is not
> fixed in the exponent. This means 1024-128=896 of the bits are known.
> Could any sieving method take advantage of this?
You wouldn't use sieving (i.e. index calculus-based algorithms) to attack
this; you'd use a "baby-step giant-step" algorithm modified to work on a
restricted exponent space. The following algorithm, which finds
x = log_g(y) given g and y, is adapted from [HAC]:
1. Split the random bits of the exponent into two halves, and let m
be the weight of the least significant bit in the upper (most
significant) half.
For example if . represents a fixed bit, * a random bit, and | the
position of the split:
...*..*|*...*
^------- weight of this bit = m = 2^5
2. Construct a table with entries (j, g^j), for j := each possible value
for the lower half of the exponent. Sort this table by second component.
(Alternatively, use conventional hashing on the second component to
store the entries in a hash table; placing an entry, and searching for
an entry in the table takes constant time.)
3. Compute g^-m and set gamma := y.
4. For i := each possible value for the upper half of the exponent,
4.1. Check if gamma is the second component of some entry in the table.
4.2. If gamma = g^j then return (x = im + j).
4.3. Set gamma := gamma * (g^-m).
The work factor is given by the square root of the number of possible
exponents (i.e. 2^64 if 128 bits are random). There may be better
attacks if the prime modulus p is not chosen carefully - ideally it
should be a safe prime, and (if I remember the most up to date advice
correctly) the base g should generate the subgroup of size (p-1)/2.
If you use a 1024-bit safe prime modulus with about 256 bits of the
exponent random, and g chosen as above, that should be secure against
passive attacks. (As always for Diffie-Hellman, protecting against
active attacks requires additions to the protocol.)
[HAC] A. Menezes, P.C. van Oorschot, S.A. Vanstone,
Handbook of Applied Cryptography,
"Algorithm 3.56: Baby-step giant-step algorithm for computing
discrete logarithms,"
[Also see Note 3.59 (restricted exponents), and the discussion at
the top of page 128.]
CRC Press, 1997.
http://www.cacr.math.uwaterloo.ca/hac/about/chap3.pdf
(Congratulations to the authors and publisher for putting this book
on the web, BTW. It's still well worth buying the paper version for
convenience.)
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBODYktjkCAxeYt5gVAQG8zAf9FBDfqeu4VKr9DX1a1te8b0rrAOxryV21
4EZoeNiZQjQAoMIDSWzUE/semC7kOMO/OBcDo7lnIYCTikDDioJkvXBmaZ+FkUbk
r/xXi2CZ2oVxjamc1R/gicMrX1sqxPoZc+5Q7ey+OKVoXE+9AvjwY6zFQ2IykwVs
l3n9+SrQcIWzhnBHPGRdxYk3DgBQATvJiyEKXPs4eTBtF63ne0syMOyulTZdw12D
EaqFbevmtr2w79tiFiX+WK6cHlYxJjN3m8jlcZ+R/Tlk1CcInNUV4Z5cCyOXRARV
dIYrHCp0b5J1oQ6116ODNfGwNHHrwGhFX3cWm+VdH62WYL2/2REXUw==
=/ZYY
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Tom)
Subject: Re: What part of 'You need the key to know' don't you people get?
Date: Fri, 19 Nov 1999 09:50:00 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 19 Nov 1999 03:37:51 GMT, Tom St Denis <[EMAIL PROTECTED]>
wrote:
>In article <8124qm$2itg$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
>> Obviously I know more about it that you no wonder you don't
>> know shit about crypto.
>
>First off, please translate the above from idiot to english.
>
You know, besides being really funny, in thinking about it, this makes
a lot more of what scott says make sense. I didn't read it in the
right dialect!
Thanks for the chuckle...
>Second, admit that your remark that the keys in the rotors being bigger
>then modern ciphers, is totally false. Because well it is.
>
>Tom
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: What part of 'You need the key to know' don't you people get?
Date: Fri, 19 Nov 1999 21:58:30 -0800
Reply-To: [EMAIL PROTECTED]
Johnny Bravo wrote:
>
> On Sat, 20 Nov 1999 00:29:12 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>
> >There are /many/ possible figures you can get for the keyspace of the
> >Enigma machine, depending on which combination of components you consider
> >to be part of the key.
> >
> >There were a number of different types of wheel employed over a period of
> >time, with differing arrangements of letters. Do you count this? Or not?
>
> I went over this in another recent message to the group. This had
> nothing to do with any of the above. The original assertion was that
> 28 wheels in fixed positions with 26 states each had over 2^128 bits
> of possible positions. This assertion is absolutely correct.
>
> This was what was replied to
> ">Assuming 26 pins per wheel you need 28 wheels to match a 128-bit
> >key. Did they have 28 wheels? I am not sure... did they?
>
> <And the reply by DS>
> are you a complete fool where did you get such a rediculus number.
> Are you stuoid enough to think that the number 26 is a binary number.
> You really are full of shit Mr Tom. Each wheel is a specail
> arrangement of 26 characters and don't forget the plug borad in the
> front of machine. "
>
==================
Johnny, please, don't be angry at Dave Scott.
Each village must have its own idiot, and this group is
no exception. On my side, I highly appreciate Dave for volunteering
to do this hard job (and a superb entertainer he is !!)
I remember, there was a period when Dave kept silence for
a couple of months, and the group lost a big part of its liveliness
and attraction.
So accept D.Scott as he is - and be thankful that he gives us all
these minutes of laughter and amusement.
Keep up to good work, Dave Scott!
Best wishes BNK
=====================================
> My reply was solely directed at calling a person "rediculus"(sp),
> "stuoid"(sp) and "full of shit" for stating something that is correct.
> log2(26^28) is indeed the fewest number of 26 pin fixed wheels you
> need to achieve at least 128 bits of possible states. If you are
> taking the wheels in random order each time, you only need 17 of them
> to reach 128 bits of state.
> If you disagree with someone you figure out where they went wrong,
> correct the mistake as you see it and maintain a civil tone. If
> instead you just launch a personal attack that makes you look like a
> complete idiot because you have no clue about what you are attacking
> in front of the entire group, you can reasonably expect a serious
> amount of flames to head your way.
>
> Best Wishes,
> Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: AES cyphers leak information like sieves
Date: Sat, 20 Nov 1999 05:52:54 GMT
On Sat, 20 Nov 1999 00:20:07 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>I certainly never said the section you placed quotation marks around.
The quotation marks weren't intended to indicate a direct quote.
However, if I've inaccurately characterized your views, I'm glad; I
much prefer it that you are not advocating such things. But David A.
Scott certainly _does_ seem to hold that kind of viewpoint, which is
why he has few admirers on this NG.
------------------------------
Date: Sat, 20 Nov 1999 05:35:00 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Apparently, Hushmail does work
=====BEGIN PGP SIGNED MESSAGE=====
John Savard wrote:
>
> A posting in
>
> jyu.ohjelmonti.coderpunks
>
> mentions
>
> http://www.hushmail.com/how_it_works.htm
>
> which seems to indicate that the resident application from Hushmail
> works basically the same way that PGP did; thus, except for the fact
> that its source isn't available,
Isn't that a big enough problem in itself?
Incidentally, although Hushmail is derived from code copyrighted by the
Cryptix Development Team (www.cryptix.org), as can be seen by decompiling
the classes that implement Blowfish and SHA-1, there is no acknowledgement
of that as required by the Cryptix General License. (It's not as if the
license is at all unreasonable - just standard Berkeley open-source.)
> and worries of that nature, there is no reason to believe that it doesn't
> "work".
I can see the following problems:
1. It requires Java to be enabled. Having had experience both of breaking
various amateur cryptosystems, and finding implementation and design
bugs in Java, I can assure you that the latter is *much* easier. Also,
the attacks you end up with are more practical (i.e. instead of
requiring lots of known plaintext to break a single message for a
cryptanalytic attack, the conditions for a Java attack are usually
easy to arrange, and the result is that you can take over the user's
machine completely).
2. At http://www.hushmail.com/tech_description.htm, it says:
# A secure one-way hash of the users passphrase (using SHA) is also
# partially sent to the HushMail server, for validation of the user at
# a later date.
This is sufficient to do an off-line dictionary attack on the passphrase.
(Compare to PGP, where the attacker has to first get a copy of the
user's keyring file.) There are protocols which could be used to avoid
this weakness (SNAPI, SRP-3, etc.), but obviously the designers aren't
aware of them, or don't appreciate that off-line dictionary attacks are
a big problem. (Also, SHA-1 is quite fast, and there doesn't appear to
be any attempt to slow it down or to use any salt.)
3. At http://www.hushmail.com/about_hushmail.htm:
# Our patent-pending, state-of-the-art technology...
A substantial portion of the cryptographic community (myself included)
won't touch anything patented if they can help it, for very good reasons
that I won't go into here. It therefore has very little chance of becoming
a standard.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBODYypTkCAxeYt5gVAQEOvgf/RsWYG5FxriT/64bg3XyDQFohMXTzppFI
dCGQn/ZxP9IWgJwVPu8hhkF3Zs8453jO48N+Asw63Kg4S1PXqDFgSdhC0cOrEoBF
BzGWMkeCBQ4YzOP0AvduAKSOw/7ZPoSU3mVtw2PFARqE/ZUcXxDquBoHts7YTB7z
pDcJSFN5ELd40IljK4tUAHt6TebWyuZPwDP8oHptcWomJPE6KEYht0MFU4fhpM2b
YSoosb/JAIHNu+BWFVwqem/CBMs1i8v3cbALpb2gLJVgERuB6svPsiE0zxreqolL
R/CV+Z9bY5Msjb+HuKT/SHXsW2kg1PHWacTYFPi9/6cC8LNRLlQDgg==
=Lyfb
=====END PGP SIGNATURE=====
------------------------------
Date: Sat, 20 Nov 1999 05:49:34 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Apparently, Hushmail does work
=====BEGIN PGP SIGNED MESSAGE=====
I wrote:
> I can see the following problems:
>
> 1. It requires Java to be enabled. [...]
> 2. [Sending a hash of the passphrase] is sufficient to do an off-line
> dictionary attack [...]
> 3. # Our patent-pending, state-of-the-art technology...
I've just noticed something else:
4. At http://www.hushmail.com/faq.htm:
# 29.Internet Explorer is asking me security questions. What should I tell
# it?
#
# Depending on security setting in Microsoft Internet Explorer, users may
# be prompted at certain points while they check their HushMail. Setting
# the security level to medium will eliminate all these warnings.
It'll also completely eliminate your security (such as it is, if you're using
Windows and IE). Don't set IE's security level to anything other than High
(or Custom with everything disabled), for each security zone.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBODY2LzkCAxeYt5gVAQHYHAgAlWUU9nWmo5kw5wKKd9Uso74gwud9BMb2
2uZa2jZt6xRakyHiO6bA5Ygi149NWFJz0fbBYF/nC1fHZTrfWeloUS3XMFfCsCHY
P4W/CTek1QM4MmaZq18wgHvSlJy61jhZYijBO0T/2WWWZ0lMhJFkhV+cFw3Myh1T
WJglc2wBg4GP0Wc8BWBiDNakcqeGCdnn1o8aooQmvr9n5sTL+DrFGOMA0gWk1IKH
jGTtA4wG65vJQHdHjmN5V/1rglNtJCd1ESTq6PhYCMy2dYRNOQWwPJ65q4pYjaCE
LfaxtTzIGCYO42xU+xdNfS6X3NuGZbtgWlkyLGClwikAaGF+smTv2Q==
=xQ3W
=====END PGP SIGNATURE=====
------------------------------
From: The Walters <[EMAIL PROTECTED]>
Subject: Re: Distribution of intelligence in the crypto field
Date: Sat, 20 Nov 1999 00:14:38 -0800
Actually, it is kind of weird how this stuff works out.
Do they have a Bletchley Park? They have a Bletchley Park in spades. The lesson
of world war two wasn't lost on them. The accumulation at Bletchley Park was
inspired. At the NSA it is directed scientifically. Which isn't to say it is
narrow. They have two draws. One is the work for national security. The other
is to work with "future" technology and an underlying body of research that
allows new research that provides a satisfaction impossible elsewhere. Does the
NSA as an institution have a greater motivation than Bill? Nah. As a community
of researchers and technologists? Yup.
albert wrote:
> > I'll have to disagree with that: not that it isn't true, but it
> > doesn't apply to the NSA. The people working there aren't trying to
> > make Bill Gates rich, they're trying to keep their country safe from
> > aggression. Thus, the NSA's purpose is one that can at least be seen
> > by some of its staff as noble - so it does have more than money to
> > work with.
> >
> >
>
> So you are trying to tell me that the NSA has more "motivation" than Bill?
> That's not the point though, the point is that intelligence is sparse as it
> is. Crypto knowledge is even more rare. I don't think NSA has a Bletchley
> Park they are growing, and even if they do, I would pit the greatest crypto
> minds of the rest of the world against them and bet you'd come out pretty
> equal.
>
> Albert
------------------------------
Date: Fri, 19 Nov 1999 22:15:50 -0500
From: M Okra <[EMAIL PROTECTED]>
Subject: Re: Distribution of intelligence in the crypto field
I think the best way to solve once and for all the questions of whether
and how far ahead NSA is of the commercial and hobbyist world of
crypto is to poll this newsgroup. Who could be dissatisfied with that?
albert wrote:
> With all the NSA discussions, I was thinking...
>
> There is very VERY little distribution of intelligence in the crypto
> field. Come on, we all know the names. Shoot, in this forum, we call
> them by first names. Eli, Bruce, Lars, Ross, Ron etc...
>
> The 80/20 rule seems more like the 95/5 rule when it comes to crypto.
> About 95% of the world's advances are done by 5% of the crypto
> community. Who breaks algorithms? The same names. This is true for
> almost every industry, and crypto is no exemption.
>
> So my point is, I have serious doubts that the NSA is THAT much ahead of
> the world. Why? Because unless they are harboring a few Bruces or
> Eli's in there, I don't see them gaining that much ground. A society
> grows as a function of how fast information takes to disciminate and the
> feedback to come back. In a government structure, that rate seems to
> be... well, be as fast as service at the DMV.
>
> I see Bruce's arguement, we know what we know, they know what we know
> AND what they know. They also have resources up the wazoo. But
> intelligence isn't something money can buy, if it was, windows would be
> the best OS... correct?
>
> Disagreements?
------------------------------
Date: Sat, 20 Nov 1999 05:45:54 -0500 (EST)
From: Mark Adkins <[EMAIL PROTECTED]>
Subject: Re: A Random Key Cipher Machine
In a previous post I wrote in part:
>Addendum: In my original post it was implied that the
>division of one sinusoidal cycle into 26 sectors should be
>performed in such a way that the amplitude remains within
>each sector for an *equal time*. Perhaps I should have
>been explicit, since some simple geographic divisions do
>not accomplish this.
That is to say, there are 2*pi radians in each sinusoidal
cycle, no matter how many cycles per second. If we divide
this figure by 26 to get 26 sectors of approximately 0.24166
radians each, then each sector represents an equal amount of
time per unit of time.
For example, if the frequency is (for simplicity) 1 Hz,
then each sector covers 1/26 of a cycle and lasts approximately
0.03846 sec. If the maximum amplitude is 1 volt (again for
simplicity), and we denote the sector number by n, with
Sector 1 starting at the beginning of a cycle, then the voltage
range within a given sector n runs approximately:
from sin[(n-1)*0.24166] volts, to sin[(n)*0.24166] volts
Then (for example) as the voltage rises from zero at the
start of a cycle toward the maximum (positive) amplitude of 1,
the range of voltages within each sector (the difference in
voltage at the start and end of the sector) grows smaller. Then
the division of the sinusoidal cycle into 26 sectors of equal
*temporal* duration would need to take this into account, so
that when sampling the amplitude at the time of a keystroke, and
deciding which sector this belonged to, the design would insure
proper operation.
In other words, the sine wave is divided into 26 arcs of equal
length, and the voltages assigned to each sector are those
which fall within those arcs. The length of a given arc is
the integral of y*dx which for the sine function y=sin(x) is
cos(x) + C. The x axis is the time axis, so setting C=0 and
substituting delta-x for x, we see that the length of any arc
travelled during a given time delta-x is the same regardless
of where the arc is on the sine curve.
This still leaves the problem of the fact that each amplitude
(voltage), except for the maximum and minimum amplitudes, is
represented twice per cycle. For example, the voltage +0.5
will occur once going up and once going down in the first half
cycle. It should be a small task for the design to keep track
of whether the voltage is rising or falling at the time a
given amplitude is sampled, however. The voltage +0.5, if
sampled, would select one of two different sectors (out
of 26), depending upon whether the voltage was rising or
falling at the time.
But given all this, it might be preferable to use a different
voltage generator than a sine wave generator for the assignment
of random key letters as plaintext keys are typed. Something
very simple and linear would suffice. Ideally the voltage would
unidirectionally cover a specific positive range (say, from
0 to +26 volts) each cycle, in such a way that when this range
is divided into 26 sectors of equal temporal duration, each
sector contains an identically sized range of voltages (in the
example, 1 volt per sector). The specific temporal duration
of each sector would of course be a function of the frequency
of this ramp function. Naturally the design would need to
take into account any delays (of microseconds) between the
end of one cycle at +26 volts, and the start at 0 volts of
the next cycle, so that if a key was struck during this
time (unlikely but possible) it would be assigned to the
first sector (or the last, since it doesn't matter which,
but not both).
--
Posted for my own amusement, since you are all figments.
Mark Adkins ([EMAIL PROTECTED])
------------------------------
** 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
******************************
