Cryptography-Digest Digest #355, Volume #12 Fri, 4 Aug 00 04:13:01 EDT
Contents:
Re: DES implementation woes (John Savard)
Re: Cracking RC4-40 in FPGA hardware (Paul Rubin)
Re: Elliptic Curves encryption ("Trevor L. Jackson, III")
Re: Small block ciphers (Mack)
Re: Enigma (Mark T. VandeWettering)
Re: OTP using BBS generator? (Bryan Olson)
Re: OTP using BBS generator? (Bryan Olson)
Re: Cracking RC4-40 in FPGA hardware (Anders Thulin)
Re: Seeking simple, free crypto app (Pegwit?) (Kerry L. Bonin)
Re: Kill my Cipher (Ulrich Kuehn)
Potential use for CipherText ("C. Prichard")
Re: Seeking simple, free crypto app (Pegwit?) (Paul Rubin)
Re: New William Friedman Crypto Patent (filed in 1933) ("C. Prichard")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: DES implementation woes
Date: Fri, 04 Aug 2000 02:10:48 GMT
On Thu, 03 Aug 2000 17:57:22 -0400, Tony Lauck <[EMAIL PROTECTED]>
wrote, in part:
>Let's not start a holy war on what's natural or strange. At least not until
>after a chance to (re)read Danny Cohen's entertaining classic paper. [1]
Oh, no. I'm just expressing a personal opinion: and, even if
big-endian is more natural to Westerners, that is still due to a
_cultural_ cause, not a fundamental one.
John Savard (teneerf <-)
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: 4 Aug 2000 03:05:10 GMT
In article <WPmi5.815$[EMAIL PROTECTED]>,
CMan <[EMAIL PROTECTED]> wrote:
>I forgot to mention...while the Word Document key is truly 40 bits (actually
>48 bits because there is some re-keying in an easy to guess way), but the
>problem is the RC4 key is actually 128 bits. You see, Word first takes the
>40 bit (48) bit document key and computes a hash of this document key and
>uses that to schedule RC4.
Hmmm, that can be a problem--what is the hash function?
>I believe SSL also uses an MD4/5 hash also so this same difficulty arises
>there.
I had been under the impression, from looking at the distributed SSL
cracking code from a while back, that there was no hash (i.e. there
was a 128-bit RC4 key that came from hashing something, but 88 bits of
it were revealed in the export cipher, leaving 40 bits to search through).
I could be wrong, but even if I am, things may still be ok.
>I don't think MD4/5 is easy to implement in hardware. (I could be wrong on
>this point!!)
I don't see either of them as being terribly hard to implement in
hardware, though nobody uses MD4 in any case. MD5 requires some
sequencing logic and 64*32 bits of magic constants, but those Xilinx
parts should still be able to handle it.
>Unless the RC4 hardware and the MD4/5 hash computation run at approximately
>the same speed, the process sort of falls apart. The hardware will just sit
>there waiting for new hashes to load.
I think they can run at comparable speed. In fact, if enough gates
are available, the MD5 phase can run a lot faster than the RC4 phase,
since it's not as serial.
------------------------------
Date: Thu, 03 Aug 2000 23:28:42 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Jerry Coffin wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
> [ ... ]
>
> > > IOW, "science", by your definition has never and probably will never
> > > exist! Humpty-Dumpty would be proud of you...
> >
> > There appears to be a difference between domains that permit experimental
> > XpXrXoXoXfX confirmation and those that do not. Sciences do this. Is it your
> > position that crypto supports experimental confirmation of strength?
>
> No, not any more than a biologist can provide experimental
> confirmation that a bird evolved from a dinosaur.
RS posed a similar issue that I've not be able to articulate coherently.
In this example I suggest that a biologist cannot provide proof (or experimental
confirmation) that birds did evolve from dinosaurs, but a biologist could prove that
birds could have evolved from dinosaurs by recreating the evolutionary sequence. A
similar proof was used to show that there is no early evolutionary gap that required
intervention to cross -- amino acids created from scratch.
The amino acid experiment is is the same principle on a molecular scale as the
bird/dino experiment would be if we had the time and resources to conduct the
experiment. But it still leaves the question open as to whether they actually did
evolve from scratch or was the primitive earth contaminated from an external
source. Only Occam is available to select from the two alternatives. I don't
consider this proof in the mathematical sense. Persuasive yes. Even convincing.
But proof, no.
Since the scientific principle is that the least complex explanation that fits all
the facts is the preferred theory, the amino acid experiment, or the bird/dino
experiment would confirm the theory of evolution in the scientific sense. But is
there anything that could prove the theory in the mathematical sense? I doubt it.
Even given a time traveler able to sample the evolutionary history at arbitrary
times couldn't prove the theory of evolution. Such a traveler could prove that
birds ancestors were dinosaurs, but not that birds _had_ to evolve from dinosaurs.
A different slant is the effect the experiment has on the theory. As above it does
not prove the theory. Does it "confirm" the theory? Only in the sense that it
confirms the _consistency_ of the theory. That the theory is not in conflict with
known laws, etc. As an existential proof of consistency it works fine.
As for crypto experiments, what are we trying to prove? It is a fact such as the
bird/dino issue which is either true of false or is it a theory which requires
interpretation such as the theory of evolution? The security of a particular cipher
may appear to be a fact, but I suggest it is more like a theory. The structure
and/or behavior of a cipher may be consistent with security, no weaknesses
(counterexamples) may be known, etc., etc. But I cannot see a way to stretch
experiment past lack of negative evidence (lack of weakness).
The power of scientific inquiry is based on the ability to predict. Do we have a
theory of strength or even a hypothesis of strength that allows us to make
predictions? Are these predictions of strength subject to experimental
verification? I don't think so. We can't even measure the strength of the ciphers
we have much less predict the strengths of ciphers yet to be designed.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 04 Aug 2000 04:44:41 GMT
Subject: Re: Small block ciphers
>Mok-Kong Shen wrote:
>>
>> Mack wrote:
>>
>> > I am more interested in the theoretical properties of a small block
>> > cipher. For example, If we change the key after every second
>> > encryption. Can an attacker find the key? Or if we change the key in
>> > some linear manner after every encryption can an attacker find the
>> > key for N encryptions where the key size is N*M?
>>
>> I believe that, if the block cipher (and hence the key size) is small,
>> the opponent will simply do brute-force, for that's easy for him,
>> while a well-designed large block cipher is impractical to brute-force
>> and he has therefore to resort to more intelligent means, if
>> available.
>
>Having the block size of a cipher small does *not* imply that the key
>size is small. An 8-bit block cipher can have as many as 256! possible
>keys. Breaking such a cipher is usually done with either some
>statistical analasys, or a codebook attack, or with known plaintext.
>Figuring out what the key is may not actually be necessary, especially
>if it uses, for example, an 16 byte key to simulate a 256 byte table.
>
>If the key is changed in a linear manner, you get something like a
>dynamic substitution cipher [I think]. If the key is changed in a
>non-linear manner, you get something like RC4/ARC4. Regardless of how
>your key-changing takes place, you're adding a significant amount of
>state, which moves your cipher out of the realm of block ciphers, and
>into the realm of a stream ciphers.
>
>
For an 8-bit block size the most effective attack may vary depending
on the size of the key and the nature of the cipher. If the key is 4 bits
then the most effective attack is likely to be brute force. If the key is
above 9 then the best attack is going to be compiling a code-book or
dictionary of possible encryptions for that key. But there may be
other possible attacks. The example I gave in another thread of this
discussion shows that with a certain amount of known plaintext it may
be possible to find the key by a non-linear analysis.
On the subject of changing keys:
Yes changing the key in a certain manner after X encryptions does turn a
block cipher into a stream cipher.
But the problems of how many ciphertext it takes to break the cipher and
how to create ciphers immune to related key attacks are still good topics
of study.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
Subject: Re: Enigma
Reply-To: [EMAIL PROTECTED]
From: [EMAIL PROTECTED] (Mark T. VandeWettering)
Date: Fri, 04 Aug 2000 04:50:59 GMT
In article <[EMAIL PROTECTED]>, Jim Gillogly <[EMAIL PROTECTED]> wrote:
>John Savard wrote:
>>
>> On Fri, 28 Jul 2000 19:17:06 GMT, [EMAIL PROTECTED] (James Pate
>> Williams, Jr.) wrote, in part:
>>
>> >Mr. or Dr. Gillogly did you develop a chess playing program back in
>> >the 1970s that was described in a refereed journal article?
>>
>> It's quite possible, as I believe he is the same Jim Gillogly that
>> first ported Adventure to C.
>
>Yes, I'm also that Jim Gillogly. I lead a full life. I've also been
>spotted at Renaissance Faire singing period drinking songs in peasant
>costume while juggling, and I've sung in Carnegie Hall. :)
Gadzooks. Are you trying to make the rest of us feel insecure about
our accomplishments? Hint: it's working! ;-)
And I thought all you did was provide the vital hints for cracking
Stage 8 of Singh's challenge. (By the way, thanks for that, it was
an excellent diversion!)
Mark
--
> Jim Gillogly
> Trewesday, 8 Wedmath S.R. 2000, 05:31
> 12.19.7.7.12, 13 Eb 15 Xul, Eighth Lord of Night
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Fri, 04 Aug 2000 05:14:50 GMT
Terry Ritter wrote:
[...]
> The alternative is to not use a "special primes" construction, and
> simply not check for having selected a short cycle.
And one gets a system that is secure in the same sense as
the original BB&S scheme.
> The probability
> of selecting a short cycle at random is extremely low, but not zero.
> So where BB&S could argue that their scheme was provably secure, the
> reduced scheme *might* not be secure, and that is a weakness.
There's no reason to think (in fact it's false) that the
BB&S scheme _with_ the long-cycle check has no sets of keys
for which the generator can be efficiently predicted. The
scheme without the long cycle test is secure in the same
sense as the scheme with the test.
> I claim it is deceptive to call the reduced scheme BB&S. It is also
> deceptive to claim that any system which we can make more secure by
> our own action is absolutely secure. Here we have a case where the
> security guarantee is factoring, but our own inaction can lead to
> allowing exactly that factoring.
So should we check that our modulus is not in anyone's
public certificate? It's a non-zero chance; we can check
the pubic directories, and it would be weak to use a key for
which someone else already knows the factors.
[...]
> The security warranty from the real Blum, Blum & Shub paper is based
> upon composites of large primes of a form which they call "special."
>
> But now we have people using the part of BB&S they like, and throwing
> out what they don't like. Do we really think the authors of the paper
> did not see that possibility and decide against it? Please.
The BB&S paper was the first important work on the x^2 mod
pq generator, but certainly not the last. The long-cycle
conditions, while arguably of interest, are not needed to
support the theorem.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Fri, 04 Aug 2000 05:42:07 GMT
Mok-Kong Shen
> For one that does not have expert knowledge in BBS, like me,
> it seems unfortunately to be difficult to know from the materials
> of past discussions in the group alone whether one party is
> absolutly right and the other absulutely wrong.
So look it up. Surely anyone can recognize the utter
slyness of the claims that the reason the major current
references don't include the long-cycle test in their
description of the generator is that the authors have simply
not read the whole paper. One could study the math and
understand why, for example HAC, describes the simpler form
of the generator; but only modest skill should enable one to
recognize that the author are not lazy nor careless, they do
understand the material, and that there's no evidence that
these allegations are other than fabrications.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: Fri, 4 Aug 2000 06:39:27 GMT
Paul Morris wrote:
> Paul mentioned that RC4-40 is used in exportable web browsers (presumably as
> part of the SSLv3) and for password protected files in Microsoft Word.
It's also used to protect Adobe Acrobat documents - .PDF files.
> Although RSA's site states that RC4 is considered strong, Paul mentioned
> that it could be broken in 'a few months' with a PIII.
Hm. There's www.pwcrack.com who seems to do a brute force search for the RC4 key
in 25 days for .PDF files. But perhaps they're doing it in paralell, or able to
use some problem in the key generation.
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia Prosoft AB, Hj�lmaregatan 3B, 212 19 Malm�, Sweden
------------------------------
From: [EMAIL PROTECTED] (Kerry L. Bonin)
Crossposted-To: alt.security.pgp
Subject: Re: Seeking simple, free crypto app (Pegwit?)
Date: Fri, 04 Aug 2000 06:33:25 GMT
If you are building an application and are interested in secure point
to point communications, and Java is acceptable, I've recently
released a cryptographic protocol package into open source you may be
interested in.
I call it [V]SPS, for VScape Secure Packet Stream, and it could best
be viewed as a streamlined SSL with a fixed, but strong cyphersuite.
Connections are created using 1024 bit DSA over Diffie-Hellman with
one or two-way signed exponentials, the master secret is expanded
according to the method described in the TLS spec, and packet
communications use HMAC/MD5 or HMAC-SHA1. Each packet can use crypto
and/or compression. Crypto is 256 bit Twofish in CBC mode.
Full source is included, and the class file is around 36k which
includes all crypto - no JCE is needed at all!
This is a component from a much larger distributed system I'm working
on and am incrementally placing into the public domain. A
complimentary package for XML based X.509 certificates will be done in
a few days and available online as well.
VSPS home page is <http://www.vscape.com/developer/libs/sps/>, this
includes download links for binaries and source, Jacadocs for all the
code, and a whitepaper undergoing incremental improvement. The
protocol is completely explained.
------------------------------
From: Ulrich Kuehn <[EMAIL PROTECTED]>
Subject: Re: Kill my Cipher
Date: Fri, 04 Aug 2000 08:41:28 +0200
Reply-To: [EMAIL PROTECTED]
Martin 'SirDystic' Wolters wrote:
> > int ky[0] = 0x00000000;
> int kp[0] = 0x8F1BBCDC; (5^0.5)*(2^30)
>
> for(i=1;i<17;i++) {
> r=kp[i-1]&((1<<32)-1);
> kp[i]=rot(ky[i-1],r);
> ky[i]=kp[i]^kp[i-1];
> }
You have not made clear where the key actually is input. And what is its
length? All you have given is a method to produce a fixed set of 16
32-bit values.
> int f(int in,int k)
> {
> int r,r2,o,o2;
> in=~in;
> r=k&31;
> o=rot(in,r)^k;
> r2=o&31;
> o2=rot(o,r2)^k;
> o2=~o2;
> return o2;
> }
Here the only nonlinearity is in the data dependent rotations. But one
can skip, say in a differential attack, the first rotation by using a
difference where the least significant 5 bits are zero.
The second rotation then uses only a subkey-dependent 5-bit portion of
the data to produce the rotation amount.
I recommend reading of all the available cryptanalysi material on RC5 as
well as the paper by (if memory serves right) Kelsey, Schneier and
Wagern on "mod n cryptanalysis".
Ciao,
Ulrich
------------------------------
From: "C. Prichard" <[EMAIL PROTECTED]>
Subject: Potential use for CipherText
Date: Fri, 04 Aug 2000 07:28:35 GMT
A new Perl script that acts as the 'man in the middle' by decrypting =
messages and re-encrypting before sending them to their destination. The =
decrypted message is not stored on the server. The main virtue of the =
arrangement is the provided convenience of not having to manage a large =
set of decryption keys or signatures.
Users of the service will register and be authenticated before setting =
their send and receive keys.
Many registered users will be able to communicate without the hassle of =
keeping track of various decryption keys. The application takes care of =
it automatically, always forwarding a message to a given destination =
using the user's receive key.
Users can login and change keys at any time without causing a mixup.
An early demonstration of the CipherText algorithm suggested that it is =
possible to develop this service using the default http protocol, making =
it seem practical.
The convenience of not having to deal with a set of decryption keys ( or =
signatures ) also makes this arrangement seem practical.
An Internet Explorer compatible demonstration at: =
http://greentv.com/cgi-bin/cgiwrap/greentv/lady_site.cgi?ciphertext_butto=
n=3D%22CipherText%22=20
allows a user to send an encrypted message to any given email address =
assuming the use of numeric key values.
Another Java-enabled browser demonstration at : =
http://greentv.com/Java/CipherText_2.html
uses greater sophistication in the CipherText algorithm where the =
encrypted message is actually 'whitened' to achieve greater message =
security.
A demonstration of an email service that combines these two =
demonstrations and does user authentication should be available soon. =
The actual Java -> Perl implementation and license to use the CipherText =
algorithm will become available for use within the US shortly after the =
demonstration is announced.
It stands to reason that if the messages are not stored on the server =
and users believe in the integrity of the implementation (possibly for =
world-wide internet use), then the arrangement will prove to be useful. =
Message content will be transmitted to any internet destination with a =
fair degree of integrity. The possible use for a D-H key exchange will =
be to improve security when authenticated users are setting their keys. =
Otherwise a key exchange is not required, as it is assumed that both =
users are registered, and their unique email addresses are then used to =
index the appropriate keys.
It may be possible to charge an annual fee for hosting the service on a =
per subscriber basis, or as stated, the Perl application could be sold =
outright.
-Charles Prichard
www.greentv.com
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Crossposted-To: alt.security.pgp
Subject: Re: Seeking simple, free crypto app (Pegwit?)
Date: 4 Aug 2000 07:29:16 GMT
In article <[EMAIL PROTECTED]>,
Kerry L. Bonin <[EMAIL PROTECTED]> wrote:
>
>If you are building an application and are interested in secure point
>to point communications, and Java is acceptable, I've recently
>released a cryptographic protocol package into open source you may be
>interested in.
>
>I call it [V]SPS, for VScape Secure Packet Stream, and it could best
>be viewed as a streamlined SSL with a fixed, but strong cyphersuite.
This sounds cool, but why not just use SSL? There's no requirement in
SSL to support multiple ciphers. What concrete advantages does VSPS have?
And how confident are you that VSPS has no protocol errors? Remember
that SSL 3.0 exists because SSL 2.0 had security bugs, and SSL 2.0
existed because SSL 1.0 had security bugs, and *all* of them had been
designed by experts and put through a peer review process before being
released into the world. Making mistakes is very easy, and departing
from a mature standard without a solid good reason seems like asking
for trouble. I've only looked at your URL for about 2 minutes, but I
don't find any of the stated reasons convincing (i.e. you make SSL sound
worse than it is), and that the signatures on key exchange components
are *optional* scares me.
If you're serious that SSL's encrypting all the data packets was
causing performance problems for your server, then something must have
been seriously wrong with your SSL implementation. Even if it was
written completely in Java, a cipher like RC4 should go very fast.
Remember that you still have to authenticate all the packets even if
you don't encrypt them, and computing those HMAC's is at least as
expensive as RC4 in any reasonable implementation. (HMAC-only might
have an advantage in the bizarre artificial Java environment where
HMAC uses a native implementation but RC4 must be written in Java).
I also believe the 36k class file is not that much smaller than, for
example, the Cryptix Java SSL implementation, though I'm not sure
whether that uses JCE. It certainly doesn't need to though.
VSPS does look like a nice piece of work. I'm just not convinced
that it's needed.
------------------------------
From: "C. Prichard" <[EMAIL PROTECTED]>
Subject: Re: New William Friedman Crypto Patent (filed in 1933)
Date: Fri, 04 Aug 2000 07:48:13 GMT
The invention makes use of the same principle I suggested to this group =
in regard to key expansion with CipherText.
Where a given key is alterred by some repeatable method so that the =
alterred key has a different length than its root. Then when both keys =
are applied to the message the resulting set of cipher combinations is =
expressed as 10 * 11 if the root key has 10 values.
A 110 character message can be encrypted without repeating the applied =
cipher sequence.
Its seems kind of like some kind of ancient Chinese technology.
-Charles Prichard
Its been 8 months since the patent application was filed on CipherText =
which uses a root key and a somehow modified version of the root key. No =
word at all yet from the patent office.
------------------------------
** 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
******************************
