Cryptography-Digest Digest #479, Volume #9 Wed, 28 Apr 99 20:13:02 EDT
Contents:
Re: Factoring breakthrough? ([EMAIL PROTECTED])
Java crypto Cipher-Block-Chaining isn't chaining (Robert Luursema)
Re: SHA vs. SHA-1 (David A Molnar)
are there any LLL analogs for (Z_2)^n ? (David Bernier)
Re: Quantum Computing and Cryptography added to web site... (Medical Electronics Lab)
Random Number Generator announced by Intel (John Savard)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(John Savard)
Re: Prime Numbers Generator (D. J. Bernstein)
Re: Block Cipher Question (wtshaw)
Re: Common Passowrds (Nathan Christiansen)
Re: Algorithms where encryption=decryption? (David Wagner)
Re: SHA vs. SHA-1 (Paul Koning)
Is this cypher weak? ("Stephane BARTHES")
Re: Encrypted Phones (Paul Rubin)
Re: break this code (Jerry Coffin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Factoring breakthrough?
Date: Wed, 28 Apr 1999 12:43:06 GMT
In article <[EMAIL PROTECTED]>,
lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
> Rumor has it Adi Shamir will announce factoring breakthrough soon.
> Increasing efficiency by orders of magnitude and breaking keys 100-200
> bits longer than current state of the art.
>
> Anybody confirm/deny?
The proof is always in the pudding.
I've grouped these claims into three categories:
1) Wacko
2) Have merit, but of limited practical use
3) Significant breakthrough
The first one is pretty self explanatory. Number two includes some of those
mathematical wonders that disclose weaknesses in algorithms under certain
circumstances. These are hard to find. They show a weakness, but only apply
to special cases which can usually be avoided or are statistically very
unlikely to occur. Number three is the prize. This is where someone
discovers a truly significant breakthrough (differential analysis comes to
mind here). These breakthroughs can pose serious threats to certain
algorithms and schemes.
As for the current claim, my bet is the "breakthrough" falls somewhere between
number (1) and number (2). The longer the suspense, the more it moves toward
number (1).
JTP
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Robert Luursema)
Crossposted-To: comp.lang.java.security
Subject: Java crypto Cipher-Block-Chaining isn't chaining
Date: Wed, 28 Apr 1999 16:28:43 GMT
Here a question for a cryptography specialist.
I just found out that the Java JCE (java Cryto Extension API) as it
is designed by Sun and implemented by many others, that its
Cipher-Block-Chaining code (for DES, DESede, idea, etc.) is not doing
any chaining between blocks of data. That is, the IV that carries the
cipher end state of previous encrypted block of data to the next one,
stays the same from block to block. It is only randomly determined
upon cipher initialization, and there is a way to set and to get it.
The IV is however not changed when encrypting data.
To me this defeats the purpose of Cipher-Block-Chaining, which
guarantees that each block (exchange) of encrypted data depends on
the previous one.
But what do you crypto specialists think about this?
Robert Luursema.
--
Please remove the NOSPAM from the reply address.
There are unfortunately still spammers out there :-(
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: SHA vs. SHA-1
Date: 28 Apr 1999 16:15:01 GMT
John Savard <[EMAIL PROTECTED]> wrote:
> http://members.xoom.com/quadibloc/mi060301.htm
> ...the difference consists of an extra circular left shift of one bit in
> the "shift register" part that expands the block of text being hashed.
It's worth noting that this difference thwarts an attack which was
presented at CRYPTO '98.
"Differential Collisions in SHA-0" Florent Chabaud, Antoine Joux
the proceedings are LNCS 1462. I think Joux has a web page, too.
-David
------------------------------
From: David Bernier <[EMAIL PROTECTED]>
Crossposted-To: sci.math.research
Subject: are there any LLL analogs for (Z_2)^n ?
Date: Wed, 28 Apr 1999 12:17:44 GMT
There are some good algorithms (including LLL) to solve
certain classes of subset-sum (or knapsack) problems in the ring
R=Z [cf. ref. 1].
Suppose we now let R be the ring (Z_2)^n , that we have
a sequence a_1, ... a_m of distinct non-zero elements of R
and a (non-zero) s in the subspace spanned by the a_i (i=1,m).
It is not assumed that the a_i are linearly independent.
The problem is to find a sequence b_1,... b_m
(all equal to 0 or 1) such that s = \SUM_{i=1,m}{b_i * a_i} .
Following the presentation in [1], we could let
e_i = i'th canonical vector in (Z_2)^(m+1), namely
e_i = (0, 0 , .... 1 , ... 0)
^ {1 in i'th place}
and look for low-weight codewords in the binary code given by the
(m+1)x(m+n+1) matrix schematically represented by:
[e_1, a_1]
[e_2, a_2]
...
[e_m, a_m]
[e_{m+1}, s]
Note: By construction, this matrix has rank m+1. There is a
non-zero codeword of weight equal to one plus the least number
of the a_i that add to give s. There could be non-zero
codewords with a strictly lower weight.
Are there "good" algorithms known and published for finding
low-weight codewords for some classes of problems, e.g. if the
generating matrix is similar to the above with a minimal weight
known to be small?
David Bernier [ [EMAIL PROTECTED] ( lll -> l ) ]
[1]@article{CosterJoLaOdScSt92,
author="M. J. Coster and A. Joux and B. A. LaMacchia and A. Odlyzko
and C.-P. Schnorr and J. Stern",
title="Improved Low-Density Subset Sum Algorithms",
journal="Computational Complexity",
volume=2,
year=1992,
pages={11--28} }
--
Ifani Gjwsnjw
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Quantum Computing and Cryptography added to web site...
Date: Wed, 28 Apr 1999 12:50:15 -0500
David A Molnar wrote:
> So if a quantum computer is built and can handle arbitrary length numbers, with
> today's state of the art, it seems that
>
> * confidential-key distribution crypto ("secret key" crypto) is still possible, but
> survives, but with longer keylengths because of Grover's algorithm. Maybe that
>kills
> smartcards?
>
> * RSA, ElGamal, and all the Integer Factoring and Discrete Log public key algorithms
>die.
> (do elliptic curves follow?)
Possibly, but you may have to go to lots more bits than the primary
field. There are "field extensions" which build up polynomials of
polynomials and convert ECC to Z/nZ. On normal computers this is
slower than the standard square root method, but it might work on
a quantum computer. Once we have them to play with, it will be
fun to check :-)
>
> * It may be possible to find some problem in NP which admits of trapdoors but is not
> efficient on a quantum computer. Maybe lattice cryptosystems take off.
For every weapon there is a counter, for every counter another weapon.
Once we have quantum computers, we'll have quantum crypto. And
lots of other really cool things too!
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Random Number Generator announced by Intel
Date: Wed, 28 Apr 1999 19:43:16 GMT
At
http://www.intel.com/design/chipsets/810/
you can find information about the new Intel 810 chipset for personal
computers. It's billed as being for "value-priced" PCs, so maybe it will
even work with a Celeron instead of just Pentium IIIs...
Anyhow, the "Firmware Hub" chip is the one with the random number
generator.
The chip apparently has a large number of security-related features, and
these features are accessible only in a controlled manner. The random
number generator is only for use when an operating system is running,
according to the documentation.
It appears this chip, like the Pentium III serial number, is not intended
to provide users with security, but to protect software and multimedia
files from piracy.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Wed, 28 Apr 1999 18:52:50 GMT
[EMAIL PROTECTED] wrote, in part:
>I'm talking about Ritter's suggestion in which the protocol
>chooses one of about 1000 ciphers at random for each message.
>It's not enough to include strong ciphers in the pool.
No, it certainly wouldn't be.
While the intent was that the protocol would only do this if the
communication was between two users each of whom was convinced that every
one of those 1000 ciphers was satisfactory, I can now see your objection to
his scheme as you have understood it.
After all, the more ciphers being considered, the greater the chance that a
user might be _mistaken_ about at least one of his choices.
However, there are ways to correct this problem, and still gain the benefit
that cracking a few major ciphers will not be enough to allow one to read
messages.
John Savard ( teneerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Prime Numbers Generator
Date: 28 Apr 1999 21:07:42 GMT
Peter Gunn <[EMAIL PROTECTED]> wrote:
> which would mean that you
> could generate all primes < 2**32 in ~2.5mins on a PII 233...
The primespeed program from http://pobox.com/~djb/primegen.html goes up
to 2^32 in 42.1 seconds on a Pentium II-350 (gcc 2.8.1 -O1, 3600 words),
or 53.7 seconds on an UltraSPARC-296 (gcc -O6 -msupersparc, 4004 words).
That's faster than reading the same data from a typical disk.
---Dan
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Block Cipher Question
Date: Fri, 23 Apr 1999 01:57:50 -0600
In article <7fntts$27r$[EMAIL PROTECTED]>, SCOTT19U.ZIP_GUY
<[EMAIL PROTECTED]> wrote:
>
> If you truely want to encrypt in 16 bit chunks with no chaining
> of any type. You could just use a straight S table for the whole
> thing. Any other type of block cipher that uses no internal state
> for history or chaining would only be a subset of what you are
> trying to do.
>
> It is very very simple.
>
Only if a very [,] very simple algorithm is used. The key can be
sufficiently complicated to case a specific block to be encrypted alike
given two keys, but for another block not to be treated the same way at
all.
The myth that keys cannot be longer than block size has been punctured for
quite a long time now; you can credit or blame me, your option, for
exposing the truth some time ago.
Chaining? Well, a overly shallow process usually used with inferior algorithms.
--
Life's battles do not always go to the stronger of faster man...
But, sooner or later always go to the fellow who thinks he can.
------------------------------
From: Nathan Christiansen <[EMAIL PROTECTED]>
Subject: Re: Common Passowrds
Date: Wed, 28 Apr 1999 16:31:18 -0600
This is a multi-part message in MIME format.
==============03DC00EA0065747E6112B979
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Where do you get a copy of the RC4 encryption algorithm?
Nathan Kennedy wrote:
>
> Dan wrote:
> >
> > How do you attack RC4 with a 40 bit key directly?
> >
>
> Try all 2^40 keys, until you get something that looks correct. RC4
> crackers aren't hard to write, on the other hand *I* wouldn't want to
> reverse engineer a data format like Word. Maybe there's a free/commercial
> program out there that does that. In any event, cracking a 40-bit RC4 key
> could take anywhere from a couple days to a month directly proportion to
> the speed of the computer times the speed of the implementation.
>
> Nate
--
Nathan Christiansen
Multimedia Programmer
HTML/Java Group
Courseware
Allen Communication
==============03DC00EA0065747E6112B979
Content-Type: text/x-vcard; charset=us-ascii;
name="nathanc.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Nathan Christiansen
Content-Disposition: attachment;
filename="nathanc.vcf"
begin:vcard
n:Christiansen;Nathan
x-mozilla-html:FALSE
org:Allen Communication
version:2.1
email;internet:[EMAIL PROTECTED]
title:Multimedia Programmer
x-mozilla-cpt:;0
fn:Nathan Christiansen
end:vcard
==============03DC00EA0065747E6112B979==
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Algorithms where encryption=decryption?
Date: 28 Apr 1999 15:24:38 -0700
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
> If you're looking for a practical reciprocal cipher, one possibility would
> be to use DES, then use an Enigma-machine type cipher with a 256-character
> alphabet, then decipher with DES with the same key.
Clever! Let me suggest a slight variant on this that eliminates the need
to implement Enigma: DES encrypt, then xor with a fixed non-zero value, then
DES decrypt with the same key. I have no proof of security, though.
Another technique is to use a Feistel cipher with a palindromic set of round
subkeys; this will automatically be self-inverse. However, I don't recommend
it, because it has a lot of fixed points (2^32, for a 64-bit block size);
they occur exactly when the block after half of an encryption is of the form
(x,x) and thus unchanged by a swap.
One person suggested to use a Feistel cipher with the same subkey in each
round. (This is a special case of palindromic subkeys.) This is indeed
self-inverse, but I recommend strongly against it, because it is susceptible
to slide attacks and thus relatively weak. (See FSE'99 or my web page.)
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: SHA vs. SHA-1
Date: Wed, 28 Apr 1999 15:24:48 -0400
Nathan Kennedy wrote:
>
> Bjoern Sewing wrote:
> >
> > Hi everbody
> >
> > I have just one question about the SHA / SHA-1:
> >
> > What is the difference between these 2 algorithm ?
> >
> > Bjoern
>
> SHA-1 is a correction, I believe typographical, not sure, which corrects a
> weakness of the SHA standard.
No, it's a substantive change.
Quoting the standard, page 1: "ShA-1 is a technical revision of SHA
(FIPS 180).
A circular left shift operation has been added to the specification ...
This
revision improves the security provided by this standard."
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Xedia Corporation, 119 Russell Street, Littleton, MA 01460, USA
! phone: +1 978 952 6000 ext 115, fax: +1 978 952 6090
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "Be wary of strong drink. It can make you shoot at tax collectors
! -- and miss!"
! -- Robert A. Heinlein, "The Notebooks of Lazarus Long"
! in "Time Enough for Love"
------------------------------
From: "Stephane BARTHES" <[EMAIL PROTECTED]>
Subject: Is this cypher weak?
Date: Wed, 28 Apr 1999 18:46:17 -0400
Hi all,
I am new to cryptography and thinking of an encryption scheme to store
software licenses. I do not want to buy some high end stuff, since I can
probably code one myself.
However, I would like to make sure that the first hacker will not sneak in
my license files and make them tell whatever he wants.
The cypher I use is as follow, It uses a stream to be encrypted and a key.
Key is any length.
Encrypt(stream s, key k)
{
// for each16 bit chuncks of stream (last chunck is not padded)
prepareencryptbuf
stream(i)=stream(i) xor Encryptbuf(i)
}
where
prepareencryptbuf
{
shift key 1 char left, use last char of encryptbuf as lsB of the new key
(first round start with key)
encryptbuf=MD4(new shifted key)
}
MD4 is the standard Message Digest 4 function.
>From what I read, the MD-4 give a random 128 bit value from any input stream
(thus is sort of a good random number generator (I am right on that?)). It
is supposed to be very difficult to compute the key knowing it MD4 digest,
so even having a plain text and its encrypted counterpart would not
compromise the key.
The above method is very simple to use and may be used to encrypt and
decrypt the message.
Can any one give me advice on the weakness of this algorythm?
Thanks for all help.
Stephane Barthes
[EMAIL PROTECTED]
note : Let me know if anything you need any further information to make the
above clearer.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Encrypted Phones
Date: Thu, 29 Apr 1999 00:01:57 GMT
William R. Bishop <[EMAIL PROTECTED]> wrote:
>Greetings,
>
> The only encrypted phones I can find are being produced by the
>federal systems division of motorola (like we should trust them?).
>
> Does anyone know of any digitally encrypted (super secure) phones
>that can be plugged in and used over standard phone lines? PGP
>phone is the closest thing I can find, but I need boxes that are
>"plug and play" (don't require a MS O.S.).
Well, Nautilus can run under Linux or Solaris, which aren't MS OS's...
but you mean you want a piece of hardware.
Depending on how many phones you need and when, there may still be
some Comsec phones around, or you could get some of the new ones if
and when they become available. These were really excellent units.
I've heard Siemens also makes some secure phones.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: break this code
Date: Wed, 28 Apr 1999 17:59:22 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> I am a student at Purdue University, and as a course project, I
> created my own encryption/decryption program. I was wondering
> if anyone would be willing to help me out with a little research.
>
> The above passage is encrypted to the following:
>
> S&i{,q$}z}rq~x*g|.\'vn{m.a~m"kz#u&}6&i|p0e}&i.o!y|ym.|$stkk$80M*
> izsm&in&u),!{x&m|o$}zzq}z?hoiz)|&myt(~~!k|gu<,Y$#g{.%!rnkzwzw
> mp&i|'!ro&!}#|h*hm.%ypvovu,&s*nmz|0qo&w%"0{szp.m0psz|zq0voymo~sl8
Assuming your encryption algorithm is anywhere even _close_ to secure,
this is _far_ too little text to use to break it. Just for the sake
of reference, to do differential cryptanalysis or linear cryptanalysis
on even a _reasonably_ secure algorithm, you're typically looking at
collecting a minimum of several megabytes of encrypted data from known
plaintext.
OTOH, just doing a quick statistical analysis of your output reveals
that it's _probably_ not in that league of security. A good algorithm
will generally produce nearly all possible output characters with
reasonably similar frequency. Running your's through a _really_
simple analysis program shows that you've left over two thirds of the
possible output values completely unused, and of the ones you've used,
the frequency of usage varies from once up to 41 times. Given the
extremely small amount of encrypted text you've supplied, it's
impossible to say much for sure, but if that pattern of usage remains
in a substantial amount of text, there's a strong chance that
statistical analysis alone will be sufficient to break the algorithm.
------------------------------
** 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
******************************
