Cryptography-Digest Digest #60, Volume #10 Mon, 16 Aug 99 18:13:03 EDT
Contents:
How good is this quadratic sieve variation? (David Harden)
Re: frequency of prime numbers? (David Harden)
Re: Wrapped PCBC mode (SCOTT19U.ZIP_GUY)
Re: NIST AES FInalists are.... (SCOTT19U.ZIP_GUY)
Re: NIST AES FInalists are.... (David Wagner)
Re: NIST AES FInalists are.... (John Savard)
Re: NIST AES FInalists are.... (John Savard)
Re: NIST AES FInalists are.... (John Savard)
Re: NIST AES FInalists are.... (David Wagner)
Re: NIST AES FInalists are.... (John Savard)
Re: NIST AES FInalists are.... (John Savard)
Re: compress then encrypt? (SCOTT19U.ZIP_GUY)
Re: CRYPTO DESIGN MY VIEW (SCOTT19U.ZIP_GUY)
Re: rsa in other fields (John Savard)
Re: KRYHA Cipher Machine Question (John Savard)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Harden)
Subject: How good is this quadratic sieve variation?
Date: Mon, 16 Aug 1999 21:20:08 GMT
FIRST OF ALL, MY EMAIL ADDRESS IS NOT WHAT IS POSTED IN THE EMAIL
FIELD. YOU CAN RESPOND TO ME AT THE PRIME-NUMBERED CHARACTERS IN THE
FOLLOWING STRING (starting from position 1='g'):
gpf@a)cXYZep_BNU1J6TWO3IDIOT@!hMORONoBUGtYmTHEaSIXTYiPENTAl9.SOFUNcBOOo%m
Suppose that you collect expressions of the form n=a+b, where a and b
are both smooth, so that a==-b (mod n) and -a*b^(-1)==1 (mod n). Then
you can collect enough relations like this and then use linear algebra
mod 2 to find a subset with a square product, so as to get (using
modular exponentiation and Euclid's algorithm to take care of negative
exponents) m^2==1 (mod n), for some integer m, with m not congruent to
+/-1 mod n if it is good. Otherwise, find more linear dependencies mod
2 from the relations collected until a good one is found.
This can be generalized to looking for expressions of the form
a*z^2+b*c^2, where z and c are integers that do not have to be smooth
because they are already squared. You can also work with 2n, 3n, and
other larger (but not much larger, hopefully) multiples of n in this.
Does this provide a framework for a faster quadratic sieve
implementation?
---- David Harden
------------------------------
From: [EMAIL PROTECTED] (David Harden)
Subject: Re: frequency of prime numbers?
Date: Mon, 16 Aug 1999 21:28:54 GMT
On Thu, 05 Aug 1999 14:56:29 GMT, Bob Silverman <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
> Jim Gillogly <[EMAIL PROTECTED]> wrote:
>> Sniggerfardimungus wrote:
>> >
>> > I ask this question here not because it necessarily relates to cryptography,
>> > but to an interest of cryptographers, prime numbers; is there any reason to
>> > believe that there are either a finite or an infinite number of primes? Even
>> > better, is there any proof either way?
>>
>> There's an infinite number of them, and an easy proof. Suppose the
>> number were finite. Then we can take the product of all the primes
>> and add one to it. This number is not evenly divisible by any of the
>> primes, since the remainder modulo each prime is 1. Therefore this
>> number is also prime
>
>
>NO! NO! NO!
>
>Why must we hear the same tired mistakes over and over?
>
>I have lost count of the number of times I have heard this
>assertion on the Internet.
>
>The resulting number is NOT necessarily prime.
>
>What is true is that EITHER it is prime OR it is divisible by a prime
>not on our original list.
>
Example: 2*3*5*7*11*13+1=509*59. This is NOT PRIME!!!!!
---- David Harden
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Wrapped PCBC mode
Date: Mon, 16 Aug 1999 22:26:44 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
..
>> 3. Doesn't delay key searches
>
>Actually it does slow them substantially-- his method is an example of an
>all-or-nothing encryption method. As such the whole file must be decoded in
>any attempt at a guess. On the other hand other such methods of achieving
>the same result exist and are substantially faster than his particular
>construction.
Well at least we agree that is does substantailly slow key searchs
and that it is an all or nothing encryption method. And that it is slow
but I think it is secure so we differ there.
But I think people fail to realize that in the real word messages between
people fall into patterns and if one is the kind of person that is real formal
and you use a weak AES type of method with the weak NSA approved chainning
then from information theory alone only the front part of file needs to be
looked at to brake the system. An all or nothing type of encryption of my form
prevents this common front end to being as large a weakness.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: NIST AES FInalists are....
Date: Mon, 16 Aug 1999 22:17:26 GMT
In article <[EMAIL PROTECTED]>, "Thomas J. Boschloo" <[EMAIL PROTECTED]> wrote:
>Patrick Juola wrote:
>>
>> In article <[EMAIL PROTECTED]>,
>> Thomas J. Boschloo <[EMAIL PROTECTED]> wrote:
><snip>
>> >
>> >The whistle blower would however send cyphertext, and would probably be
>> >very extensively monitored. This would give him away. It is ok for
>> >people like you and me to use anonymous remailers, but probably not for
>> >them.
>>
>> This is nonsense. Contrary to popular belief, the NSA is populated
>> by human beings; I lived one floor above an NSA spook while I was in
>> college. Even back then, if he had really wanted to blow the whistle
>> on anything, he could simply have waltzed into the computer room of
>> the local community college and "social engineered" an Email account;
>> now he can simply waltz into the local internet cafe and send mail
>> to anyone he wants.
>>
>> And if he was serious enough about the whistle he was blowing, there's
>> always the news desk at the Washington Post.
>
>I obviously had a flawed picture of how the NSA works, I thought their
>every move would be watched until they retired. And then they would be
>sworn to secrecy. Been watching to much James Bond, I am afraid. I hope
>the people at the NSA have read '1984' by George Orwell however..
>
I don't think there every move is monitored especailly if they are chinese.
Only becasue it would look like they are attacking a minority. The govenment
is piss poor about using what information it does have. Just recently the
FBI admitted that the Scientist working in the H-bombs had a signed a wavier
and they could have searched his computer any time. I thought this was obvious
to anyone who ever worked with clearenaces. If the FBI is to stupid to know
this about someone working on A-bombs do you think the guy in charge of
watching people that work for the NSA are any better. That being said I don't
think it is worth the risk of being caught to give a way secrets. If the NSA
has any thing of value it is not going to the public sector it is going to the
Chinese.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NIST AES FInalists are....
Date: 16 Aug 1999 14:15:06 -0700
In article <7p9us8$o4s$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> In article <7p6pud$1u4$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (David Wagner) wrote:
> > Well, I see your point, but as network speeds increase, in the future
> > obtaining 2^36 blocks may not be so unthinkable as you imagine.
>
> My point is that a protocol should not encrypt billions of blocks with
> the same key, no matter how fast the connection and no matter how
> trusted the symmetric cipher.
Well, already today we have gigabit networks, and it's not a stretch
to imagine terabit networks where using a key for a second already
means you've used it for encrypting billions of blocks.
It's arguably implausible, but on the other hand, AES is intended to
be used for many decades. Remember the 640k barrier.
(I think a reasonable person could take either side of this debate;
I'm just trying to outline the usual argument why 2^30 attacks are bad.)
> As you know, Frog allows for as many different wirings as there are
> keys, for example 2^128 wirings for a 128 bit key. The whole point is
> that it should be very difficult to analyze them all. I know this goes
> against the accepted wisdom that equates a cipher's strength with the
> quality of its analysis, but it is a fact that the cost of breaking a
> cipher includes the cost of analysing it.
This is fine when the enemy's cryptanalysis resources are smaller than
your own. But, when we have less analysis resources than the adversary,
we're in a bind, and it'd be really nice to have an easy-to-validate
cipher that even us stupid academic folks can see is secure, without
having to worry that those brilliant NSA folks can see a clever shortcut.
> Maybe the best is to combine both worlds: mix in a cipher parts that
> have fixed wiring polished against known attacks, with wiring that is
> keyed.
I like this approach a whole lot better. Use enough rounds with fixed
wiring to ensure that the cipher is secure against known attacks, then
take on some rounds with keyed wiring as extra insurance. Sounds promising!
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST AES FInalists are....
Date: Mon, 16 Aug 1999 21:39:50 GMT
Matt Curtin <[EMAIL PROTECTED]> wrote, in part:
>No matter how many Smart People NSA hires, there will be more Smart
>People outside of NSA.
But how many of them will be paid full time to work on cryptography?
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST AES FInalists are....
Date: Mon, 16 Aug 1999 21:43:42 GMT
Lee Winter <[EMAIL PROTECTED]> wrote, in part:
>[EMAIL PROTECTED] wrote:
>> There is no doubt in my mind that NSA is much more advanced in
>> cryptology than the public sector - people who know what they can do
>> keep approving their gargantuan budget, which means that they are
>> earning it.
>Do you feel the same way about the Department of Agriculture, Energy, or
>Housing and Urban Development? Talk about a logical error!
But the NSA has to do its job right to meet the needs of those who are
paying the bills. Other government agencies, like the Post Office, are
instead within a more conflict-filled dynamic.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST AES FInalists are....
Date: Mon, 16 Aug 1999 21:37:28 GMT
[EMAIL PROTECTED] (David Wagner) wrote, in part:
>I'd claim that if your cipher allows for 2^20 wirings, that should
>probably be viewed as 2^20 ciphers which must all be validated. Unless
>you do something clever, analyzing a set of 2^20 wirings will always be
>harder than analyzing one wiring.
That may be the case with respect to FROG, or not.
But I've admired the rotor machine SIGABA because of the extra
complication and difficulty of analysis moving the main rotors by
other rotors instead of gears introduces.
Changing the behavior of a block cipher in a deeper way than just
changing subkeys that are XORed in changes it seems to me, at least,
to be highly attractive.
In my Quadibloc II design, which I came up with after learning a great
deal from examining the AES candidates, I've illustrated a way in
which this sort of thing might be feasible. I use three different
encipherment structures - a whitening round involving 16-bit miniature
block ciphers, a set of short rounds for fast diffusion, and a normal
round which involves a variant of the normal Feistel structure (the
f-function of one of four subblocks performs a function similar to
that of the extra bits created by the expansion permutation of DES,
controlling the nonlinear part of the cipher). Only between complete
groups of rounds - like pairs of rounds in DES - of different ciphers
do I include a key-dependent byte transpose.
The theory is that since the components are very different,
re-ordering the bytes should not create exploitable structure in any
case.
Of course, a more sophisticated key schedule, in which the subkeys for
each encipherment structure were effectively independent (by using a
hash-type noninvertible function) would improve the confidence in such
a scheme.
Another possibility is simply to use outer rounds of a well-understood
type, and hidden in the inner part of the block cipher, use more
difficult to analyze constructs.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: NIST AES FInalists are....
Date: 16 Aug 1999 14:21:07 -0700
Right. But, remember the lesson of RDES. Randomized wirings can really
destroy a design if you're not careful.
(RDES was a DES variant that decided whether to do the swap or not after
each round based on another key bit. I think the idea was to extend the
key length of DES. In any case, Biham & Shamir showed that the result is
very much less secure than DES against differential cryptanalysis, for
almost all of the keys.)
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST AES FInalists are....
Date: Mon, 16 Aug 1999 21:56:24 GMT
Helger Lipmaa <[EMAIL PROTECTED]> wrote, in part:
>'about every trick' sounds tricky, doesn't it? The cipher was apparently
>designed by several different people, and all the ideas were poored in. The
>result may be secure but it looks ugly.
I'll have to admit, though, I think that a secure cipher should look
ugly. Otherwise, one is throwing all one's eggs in one basket.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST AES FInalists are....
Date: Mon, 16 Aug 1999 21:53:04 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
>And please don't talk vaguely about "back doors" -- while
>they are possible in some circumstances, for an open system
>like the AES it is not at all evident that it is possible.
I quite agree. It is not at all evident that a publicly described
algorithm can be weak in some well-hidden manner.
I suppose, though, that before anyone had known about differential
cryptanalysis, LUCIFER would have seemed impressive. But hiding a
trapdoor that way - design a cipher to be weak against an advanced
attack not publicly known yet - risks backfiring. After all, it was
public interest in DES that led to the open discovery of differential
cryptanalysis.
Part of the trouble, though, is just as I can't prove designing an
algorithm to be defective in some strange fashion is possible
(although there is enough concern that it _might_ be that people
proposing block cipher algorithms generally don't include S-boxes
without an explanation of their derivation) neither can I provide a
convincing demonstration that it isn't.
Drawing the line between skepticism and paranoia can be difficult at
times.
In any event, DES and SKIPJACK do have another kind of back door. Lop
off a few rounds from SKIPJACK, and it becomes insecure. (Of course,
removing one round from DES or SKIPJACK makes it insecure because a
rule-of-thumb is violated, leaving an asymmetric design, so that
doesn't count as evidence of any mysterious characteristic.) Change
DES to have sixteen independent subkeys, and it only becomes as strong
as if its key was 65 bits long.
Hence, it is difficult to use either DES or SKIPJACK as the basis for
a scaled-up design which is much stronger, and changing either risks
weakening the cipher considerably.
That kind of limitation - involving no false promises - does seem to
appear, therefore.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: compress then encrypt?
Date: Mon, 16 Aug 1999 22:50:56 GMT
In article <7p9r04$ec9$[EMAIL PROTECTED]>, "Base2" <[EMAIL PROTECTED]> wrote:
>
>> It may be worthwhile pointing out that compression AFTER
>> encryption is essentially impossible. Or it should be -- if
>> the encrypted text can be compressed, something is likely
>> wrong with the crypto.
>
>Well then, by that theory, compressing after encryption isnt a bad way of
>checking how secure it is....
Actaully if you have a low entropy input file "english text" and you
encrypt with a method that does not change the file length. Then you
better hope that when you run a compression program on the file
that is gets bigger on the average. IF it gets smaller it could be a fluke
but if you do several files and see more than one that is smaller at all
I would say your encryption routines SUCKS big time.
>
>But in my mind, with the correct key and message, you could easily get
>repeated data ect... or depending on how you did it.
>
>I can see how an incredibly large amount of repeated (encrypted) data, then
>compressed with some form of LZ might definitly show some holes.... but
>using something such as huffman, which does hash tables of each "char",
>doesnt yeild repeated information much at all.
Actually you should use several different types of compression programs
if any of them show that the file is getting smaller then you have big
trouble. I was thinking about useing the BWT transfom to see patterns but
was wondering if any one has tried this using bit postions instead of the
standard character.
>
>So in my idea of all this bullshit, doing a simple huffman encoding on the
>encrypted message, helps greatly, only if the interceptor of the message
>doesnt know that you are compressing it (or even making it longer [with the
>case of huffman encoding on data with no repetition] ).
Yes just as SKIPJACK was a secrect method. Half the battle is sometimes
just finding out how the code was encrypted. IF you and a friend decided
in secret to first PGP the message than compress with a huffman encoder
then enctypt with DES anad then did a huffman encorder again. It would
most like be very secure in the sense that they don't know what you did.
If an attacker does not know what you did it is much harder to break.
>
>Of course, if you want to take that if statement into consideration, if the
>interceptor of the message knows how your encrypting your data, and when you
>are compressing ect... it really does no good to compress, because it doesnt
>hide any information anyways.
>
True if the attacker knows your outer pass was compression then it
would not help. However if you used something like my compression
as an outer pass. The odds are they would never even test to see if it
was compressed. In which case it would then be even harder to tell
which encryption method was used. I am sure NSA types look for
characteristics such as headers and such to get a handle on breaking
stuff. That being said I have sent many many message and I had trouble
with email or something changing them since the system thinks they
are files of one type or another so I alwasy try to use ZIP as the last
phase which makes the file longer but is is easier to send and to
check the data with the outter ZIP envolope. It is foolish to make
your checksums part of the encryption. Let ZIP handle that.
Also while you at reverse the file at some point they are not
smart to check for compression done in reverse since 99.99 files
are always encrypted front to back. In case people have not
noticed scott19u.zip is wrapped but you have to look at data
form the back of file to the front when decoding. Nobody likes
that.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: CRYPTO DESIGN MY VIEW
Date: Mon, 16 Aug 1999 22:06:02 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]>
wrote:
>SCOTT19U.ZIP_GUY wrote:
>>
>
>> are many such methods. I have been looking most recently
>> at using the BWT method and thought I was close to getting it to
>> work but my requirement that every file even if the wrong file should
>> be a valid compressed file so no information in sturcture could be
>> used by attacker to tell if it is a valid file.
>
>I don't see how you requirement can be realized. If you have a file
>A compressed to B and the last symbol written to B consists of, say,
>4 bits. If I delete the last bit of B to become C, then on
>uncompressing C the software will find the last 3 bits of C that it
>can't decode. So this 'wrong' file C obvioulsy will be determined
>to be an invalid file. Or do I miss something?
>
>M. K. Shen
AS usual you don't understand and I am not sure that I can help you
I don't want to go on forever with you like I have in the past.
But TAKE A LOOK AT THE CODE. YOU HAVE THE PROGRAM.
That said lets see if I can help. The files invovled are all wirtten
in a whole number of bytes. So you can't delete "one bit".
It may be the case that when you compress a whole file that
the symbols just fight nicely into the output file. Then there
may not be a ending problem. What you may be asking
is what happens if the last symbol compresses such that it
would normal fill only a partial number of bits. In that case
something must be done. since I have to but something there
if I am to use that byte at all.
A first attempt might be to wirte zeros in the trailing bit positions.
Since it is easy to constuct the dynamic huffman table such that
the "all zero token" would be 8 or more zeros this would seem
like a fix. However though this may be what you want it is not
and is only good for a first approximation. Since the zero fill
solution is not the optimal one to use in that you can still
make the file shorter on the average by not just useing the
zero fill option. Also it does not meet my crieteria that any
file most be a valid compression file. So it is not the
best soultion by several counts.
If your still lost see what I did. It is not to hard to test the
code and then you can see how I ended them. Its in the
code and it works my friend.
If what I did is impossible don't just that you think it
is impossible. Find an example!!
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: rsa in other fields
Date: Mon, 16 Aug 1999 22:00:20 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote, in part:
>All of today's public key algorithms operate in some cyclic group.
>If one could indeed embed an elliptic curve encryption algorithm in
>a field, it would be a lot easier to break. It would reduce to
>solving an ordinary discrete log problem for which we have index
>calculus attacks.
One of the elliptic curve algorithms is an analogue of Diffie-Hellman.
Because of not being a field, it is believed that one can get away
with shorter keys.
I suppose what he was looking for - without the mathematical
sophistication to know if it was possible or not - was the elliptic
curve (or Lucas function, etc., etc.) analogue of RSA. Are any such
analogues possible?
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: KRYHA Cipher Machine Question
Date: Mon, 16 Aug 1999 22:03:02 GMT
[EMAIL PROTECTED] (John Savard) wrote, in part:
>It is sufficiently limited that I didn't even deign to put information
>about it up on my web page, IIRC.
I didn't remember correctly. It is briefly discussed at
http://www.freenet.edmonton.ab.ca/~jsavard/ro020102.htm
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.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
******************************
