Cryptography-Digest Digest #913, Volume #10      Sun, 16 Jan 00 06:13:01 EST

Contents:
  Crypto Regulations (Guy Macon)
  Chosen/Known/Biased Plaintext (Guy Macon)
  Re: Chosen/Known/Biased Plaintext (fvw)
  Re: Chosen/Known/Biased Plaintext ("Douglas A. Gwyn")
  Re: Forward secrecy for public key encryption (Scott Contini)
  Re: LSFR ("Marty")
  Distributed.net completes CSC challenge ("dave avery")
  Re: Crypto Regulations ("Ryan Phillips")
  Cryptanalysis of R.A.T (Scott Contini)
  can someone encrypt for me? (Cutedoggy99)
  Re: Changing ARC4's State-Space Size ("r.e.s.")
  Re: A Hash Function Application (Mok-Kong Shen)
  Re: can someone encrypt for me? (Guy Macon)
  Re: Cracking DES (Paul Schlyter)

----------------------------------------------------------------------------

From: [EMAIL PROTECTED] (Guy Macon)
Subject: Crypto Regulations
Date: 15 Jan 2000 23:19:36 EST


I was just wodering; if a commercial vendor keeps most of his code secret
but publishes the source code for just the crypto algorithm, would he
be free to export his product without restriction?


------------------------------

From: [EMAIL PROTECTED] (Guy Macon)
Subject: Chosen/Known/Biased Plaintext
Date: 15 Jan 2000 23:30:41 EST


While searching around trying to learn, I ran into the
occasional reference to Chosen Plaintext, Known Plaintext,
and Biased Plaintext (biased meaning that the attacker
knows that some bit patterns cannot be in the plaintext
(No FF bytes in pure 7 bit ASCII) or some way that the
plaintext is correlated (Q followed by U) - a good
encryption system should be resistant to all three.

My question is whether Chosen Plaintext is better than
Known Plaintext for mounting an attack.  What are the
practical differences in real life?


------------------------------

From: [EMAIL PROTECTED] (fvw)
Subject: Re: Chosen/Known/Biased Plaintext
Reply-To: [EMAIL PROTECTED]
Date: Sun, 16 Jan 2000 04:45:09 GMT

In <85rhhh$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
>While searching around trying to learn, I ran into the
>occasional reference to Chosen Plaintext, Known Plaintext,
>and Biased Plaintext (biased meaning that the attacker
>knows that some bit patterns cannot be in the plaintext
>(No FF bytes in pure 7 bit ASCII) or some way that the
>plaintext is correlated (Q followed by U) - a good
>encryption system should be resistant to all three.
>
>My question is whether Chosen Plaintext is better than
>Known Plaintext for mounting an attack.  What are the
>practical differences in real life?

Yes, chosen plaintext is better than know plaintext. This is because with most
algorithms certain plaintexts give more info about the key than others.

Note there are also adaptive-chosen-plaintext attack's (you can encrypt 
something, study it, than encrypt something else you chose on the basis of your
study.... repeat), chosen-ciphertext attack (you get to choose the ciphertext
and get the corresponding cyphertext), Chosen-key-attack (You have some 
knowledge about the relationship between different keys. According to 
Applied crypto (A book I can definately advise), this is "Strange, obscure,
not very practical and discussed in section 12.4").
And, last, and least too I guess, cyphertext-only attack. Not nice.


-- 

                        Frank v Waveren
                        [EMAIL PROTECTED]
                        ICQ# 10074100

------------------------------

From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Chosen/Known/Biased Plaintext
Date: Sun, 16 Jan 2000 05:52:34 GMT

Guy Macon wrote:
> My question is whether Chosen Plaintext is better than
> Known Plaintext for mounting an attack.

As usual, it depends on the specific cryptosystem.

A classic example was the identification of a code group
as meaning one of two enemy bases.  An attack was ordered
against one of the bases, and when the attack was reported
in that code it was now clear which base the group meant.

More generally, consider encrypting each of the following
(chosen) PTs:
0000000000000000000
1000000000000000000
0100000000000000000
0010000000000000000
0001000000000000000
etc.
The difference between the first CT and each other CT
characterizes the effect of each input bit.  (We used to
call this "tickling" the system.)

------------------------------

From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Forward secrecy for public key encryption
Date: 16 Jan 2000 05:57:24 GMT

In article <85rb0t$sl$[EMAIL PROTECTED]>,
David Wagner <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
>lcs Mixmaster Remailer  <[EMAIL PROTECTED]> wrote:
>> The latter idea was proposed by Adam Back on the Cypherpunks list on
>> May 31, 1998:
>> http://www.inet-one.com/cypherpunks/dir.1998.05.25-1998.05.31/msg00171.html
>> 
>> The ensuing discussion did not seem very promising, though.  It was hard
>> to find a scheme where the key holder had a significant edge.
>> 
>> He needs to be able to compute discrete logs efficiently while making
>> sure that an attacker who may have vastly greater resources could not
>> factor the modulus or compute discrete logs.
>
>Here is an idea for an improvement which I didn't see on cypherpunks.
>
>Adam's original scheme exploits the gap in complexity between factoring
>n=pq and taking discrete logs mod p,q.  The problem is that there's
>not a big enough gap between the two: we'd like to use a 1024-bit n for
>adequate security, but then taking discrete logs mod 512-bit primes is
>too hard for routine use.
>
>But what if we choose n as the product of, say, four primes, n=pqrs?
>I *think* that known factoring algorithms aren't any better at factoring
>product-of-four-prime composites than they are at factoring RSA-composites
>of the same size.  If I got that right, we'd only need to do discrete
>logs mod 256-bit primes to use a 1024-bit n, and that sounds a little
>more realistic.
>
>Can any of our resident factoring experts confirm or refute this?

The running time to find a factor  p  with ECM is order

    e ^ { (1 + o(1)) sqrt[ 2 * log p * log log p ] }

Using ECM to find a 256-bit prime factor is certainly faster than
using number field sieve to factor a 1024-bit number.

To compute a discrete log modulo  p  using the linear sieve or the 
the gaussian integer sieve, it takes order:

    e ^ { (1 + o(1)) sqrt[ log p * log log p ] }

So there still is a gap, but maybe not insurmountable for the
size numbers you are suggesting (256-bit primes).  Of course,
discrete logs can asymptotically be computed faster using the number
field sieve discrete log alg, but according to Antoine Joux and
Reynald Lercier, in practice it doesn't seem to pass up the other
algorithms to about 100 digits (I downloaded a presentation by them
from a Waterloo web site).

Ok here are some stats which also come from Joux's and Lercier's
presentation.  256-bits is approx 78 digits.  In 1996, D. Weber
used the Gaussian Integer sieve to solve a discrete log modulo
a 85-digit prime in 30 mips years.  A 78-digit prime should be
approx 1/5 times as hard, so a 78-digit prime should take about 6
mips years.

What about ECM?  Near the end of last year (1999), Nik Lygeros and Michel
Mizony posted a record factorisation with ECM - a 127-digit composite was
factored into a 54-digit prime and a 73-digit prime.  I don't see
a CPU time on the posting, which is available at:
http://www.loria.fr/~zimmerma/records/p54
However, finding a 78-digit prime should be order 4000 times harder
than finding the 54-digit prime.

I haven't read Adam Back's idea, but I would think that the gap
between solving discrete logs modulo a 256-bit prime and discovering
a 256-bit factor of a 1024-digit number is not large enough for
a security application.  It also should be pointed out that finding
the discrete logs can be done, but it takes some effort - 5 mips
years is not negligible!  And on top of that, you need to be able
to solve a reasonably large matrix modulo  p - 1 , which is not so
easy.

Scott









------------------------------

Reply-To: "Marty" <[EMAIL PROTECTED]>
From: "Marty" <[EMAIL PROTECTED]>
Subject: Re: LSFR
Date: Sat, 15 Jan 2000 23:25:56 -0800

Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Marty wrote:
> > A fairly easy approach that keeps the logic fairly simple is to use a
> > group of LSFR's that have relatively prime periods and are short
> > enough to have reasonable sized lookup tables. Just clock them
> > in parallel.  Knuth, Vol 2 gives an algoritm for reconstructing the
> > original count in the section on modular arithmetic.
>
> As far as that goes, you could run a bunch of rings each of which
> circulates a single "1" bit one position per tick.  If the rings
> have relatively prime sizes, and sampling determines where the
> "1" bit is in each ring, the CRT will tell you how many ticks
> since the previous sample.

Yep, that is sort of the ultimate in simplicity though the approach,
being a "one-hot" state machine design, is resource intensive. The
proposed approach though is nearly as state efficient as the
original LSFR and while it requires more taps, has the same high
speed clocking capabilites.

-Marty




------------------------------

From: "dave avery" <[EMAIL PROTECTED]>
Reply-To: "dave avery" <[EMAIL PROTECTED]>
Subject: Distributed.net completes CSC challenge
Date: Sun, 16 Jan 2000 00:56:53 -0700 (MST)

Greetings!

I'm very proud (and quite relieved) to announce that distributed.net
has successfully met the CS Communications & Systems CSC encryption
challenge.  The key was submitted to CS Communications & Systems
just moments ago.

At 06:26:52 on 01/16/00, we received a success key, 00438EF36FE3FC21.
I haven't contacted the user yet, so I can only say that the computer
that found the machine was a Sparc box running Solaris and version
v2.8002 of the client.

Users can expect an official press release with far more information
and statistics within a few hours.  Please standby for more details.

Thanks again for all your support and dedication.

Daniel Baker
[EMAIL PROTECTED]




------------------------------

From: "Ryan Phillips" <[EMAIL PROTECTED]>
Subject: Re: Crypto Regulations
Date: Sun, 16 Jan 2000 00:05:20 -0800

With the new crypto regulations you can do that:

Swiped from Mike Rosings post:
3. Also in 740.13, to, in part, take into account the "open source"
approach to software development, unrestricted encryption
      source code not subject to an express agreement for the payment of
a licensing fee or royalty for commercial production or sale of
      any product developed using the source code can, without review,
be released from "EI" controls and exported and reexported
      under License Exception TSU. .... To qualify, exporters must
notify BXA of the Internet location (e.g., URL or Internet address) or
      provide a copy of the source code by the time of export. These
notifications are only required for the initial export; there are no
      notification requirements for end-users subsequently using the
source code. Notification can be made by e-mail to
      [EMAIL PROTECTED]


Guy Macon wrote in message <85rgso$[EMAIL PROTECTED]>...
>
>I was just wodering; if a commercial vendor keeps most of his code secret
>but publishes the source code for just the crypto algorithm, would he
>be free to export his product without restriction?
>



------------------------------

From: [EMAIL PROTECTED] (Scott Contini)
Subject: Cryptanalysis of R.A.T
Date: 16 Jan 2000 08:26:09 GMT

Earlier this week, a cipher called "R.A.T." was posted on this newsgroup.
This cipher is very weak, and I will show here how to cryptanalyze it.
I remark that somebody else named Poncho gave an argument that it is
weak, but my attack is simpler.  The original positing of the R.A.T.
cipher is at the end of this post.

My attack is a known plaintext attack - I assume you know plaintexts
and their corresponding ciphertexts.  However, to simplify explanation,
I will present it as a chosen plaintext attack, and I leave it to you
as an exercise to convert it to known plaintext.  The attack is
essentially the same in both forms.

Here is (one reason) why the R.A.T. cipher is weak:
    Whenever a ciphertext byte equals its plaintext byte,
    you learn one byte of the key.

Here is how the cipher algorithm works ( "^" means exclusive or):

    initialise:  A[0] = 0, B[0] = 128

    for i = 1 to the number of plaintext bytes {
        Let X[i] = i'th plaintext byte
        A1 = X[i] ^ key[ B[i-1] ]
        B[i] = A1 ^ key[ A[i-1] ]
        output B[i] as the i'th byte of the ciphertext
        A[i] = A1
    }

The key is a permutation of 0, .., 255  (the author also specifies
that it has no fixed points, but the exact key generation algorithm
is not given).

In general, at iteration  i  we have:

        B[i] = X[i] ^ key[ B[i-1] ] ^ key[ A[i-1] ]
        A[i] = X[i] ^ key[ B[i-1] ]

For simplicity of explanation, we will assume all the input bytes
are 0 (this assumption is not needed).  In this case, we have

        B[i] = key[ B[i-1] ] ^ key[ A[i-1] ]
        A[i] = key[ B[i-1] ]

Suppose the  i'th  byte of the ciphertext is 0 (i.e.  B[i] = 0).
Then
        0 = key[ B[i-1] ] ^ key[ A[i-1] ]
Since the key is a permutation, we must have that
        B[i-1]  equals  A[i-1]
But, we also know that
        A[i-1] = key[ B[i-2] ]
So, substituting the previous equations, we have:
        B[i-1] = key[ B[i-2] ]
Remember that the  B  values are ciphertext values that we see as
output.  So we know  B[i-1]  and  B[i-2] , and hence we now know
key[ B[i-2] ].

This is the first attack that came to my mind.  There may be simpler
attacks, but this shows that R.A.T. is a very weak cipher and should
not be used in any security application.

Scott


========================================================================
========================================================================
========================================================================

>From [EMAIL PROTECTED] Sat Jan 15 16:39:42 EST 2000
Article: 56990 of sci.crypt
Path: 
news.usyd.edu.au!news1.optus.net.au!optus!intgwpad.nntp.telstra.net!newsfeed.berkeley.edu!ihug.co.nz!news.tig.com.au!p15-nas7.syd.ihug.com.au!satan
From: Jeff Lockwood <[EMAIL PROTECTED]>
Newsgroups: sci.crypt
Subject: My Encryption system
Date: Sat, 15 Jan 2000 12:01:38 +1100
Organization: The Internet Group (Sydney)
Lines: 89
Message-ID: <[EMAIL PROTECTED]>
NNTP-Posting-Host: p15-nas7.syd.ihug.com.au
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Server-Date: 15 Jan 2000 01:01:23 GMT
X-Sender: [EMAIL PROTECTED]
Xref: news.usyd.edu.au sci.crypt:56990


         Description of my R.A.T. encoding and decoding system



Notes:
 
  all values and variables mentioned in this document will be single byte
  quantities , with values ranging from 0-255.

  the key is an array of 256 bytes; containing all all the possible values,
  sorted into a random order, with one extra requirement: the value contained
  in each cell of the array cannot be the same as the index number of the cell
  eg: cell 0 cannot contain 0, cell 1 cannot contain 1 ,... 



  Variables:

    X  This contains the data byte to be encoded
    A  This is used as an index into the key array
    B  This is used as an index into the key array, and for 
       the encoded output byte.
    A1 This is used for temporary storage
    B1 This is used for temporary storage


The Encode function:

    1) Initialise variable A with the value 0 and B with 128. 

    2) read 1 byte into X.

    3) The value in X is XORed with the byte in the key indexed by B,
       and the result is stored in A1.

    4) The value in A1 is XORed with byte in the key indexed by A,
       and the result replaces the value stored in B.

    5) Write out the the byte in B

    6) Replace the value in A with the value in A1

    7) Loop back to step 2 until all bytes have been encoded.


The Decode function:


    1) Initialise variable A with the value 0 and B with 128. 

    2) read 1 byte into B1.

    3) The value in B1 is XORed with the byte in the key indexed by A,
       and the result replaces the value in A.

    4) The value in A is XORed with the byte in the key indexed by B,
       and the result is stored in X.

    5) write out the value in X

    6) replace the value in B with the value in B1.

    7) loop back to step 2 until all bytes have been decoded.
 


Aditional notes:

  The above functions are relesed into the public domain. You may use them
  in any program (even commercial ones). they may also implemented directly
  in hardware. I place no restrictions upon their use.

  I also release this document into the public domain and permit distribution
  without any restrictions.


        Jeff Lockwood    January 8 2000

I have also written a simple C program to demonstrate these routines, and
posted it in sci.crypt on the 8th of january


Jeff Lockwood <[EMAIL PROTECTED]>

PGP public key:

  homepages.ihug.com.au/~satan/pgpkey.asc




------------------------------

From: [EMAIL PROTECTED] (Cutedoggy99)
Subject: can someone encrypt for me?
Date: 16 Jan 2000 08:48:27 GMT

Could someone please encrypt this url address for me in crypto version 0: 

http://www.cutedoggy.com/sponsors/

------------------------------

From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Changing ARC4's State-Space Size
Date: Sun, 16 Jan 2000 01:39:09 -0800

"r.e.s." <[EMAIL PROTECTED]> wrote ...
[...]
: as far as I know, there have been no published
: analyses of the Solitaire algorithm.
[...]

Oops...
Paul Crowley posted his empirical findings of some
apparent bias in Solitaire, and also pointed out the
irreversibility of the algorithm.

(Maybe I was thinking of the analyses that its author
has hinted may be forthcoming.)

r.e.s.



------------------------------

From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A Hash Function Application
Date: Sun, 16 Jan 2000 11:08:52 +0100

John Savard wrote:
> 
> Each message sent is accompanied by a session key, sent in any
> convenient encrypted form (by conventional public-key techniques, or
> enciphered by a key-exchange-key which is also a shared secret).
> 
> The large key is then encrypted by the session key, and then a one-way
> hash is used to produce the actual long key used to encrypt the
> current message.

I guess that implemtnted/employed properly your scheme can be used
in practical applications, i.e. when it is judged by the user to 
offer sufficient practical security (using some more or less 
'subjectivity') for him. Typical problems with evaluating such 
schemes consist in my view in the fact that on the one hand it 
'appears' not to be extremely secure (i.e. comparable to the
currently 'established' 'very secure' ones) and on the other hand 
it seems difficult to 'compute' its security/insecurity because its 
design doesn't conform well enough with the 'mainstream' to offer
easy/ready ways of discussions. That's why your idea isn't likely 
to be examined/scrutinized by the experts, I am afraid.

M. K. Shen

------------------------------

From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: can someone encrypt for me?
Date: 16 Jan 2000 05:33:50 EST

In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] 
(Cutedoggy99) wrote:
>
>Could someone please encrypt this url address for me 
>
>http://www.cutedoggy.com/sponsors/

Sure!

9C5D8077ACFC40507512BD1AC17AEF7C235EE9D2A3CF6148B16A2213E0B71A56A382

I hope this helps...



------------------------------

From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Cracking DES
Date: 16 Jan 2000 10:57:08 +0100

In article <[EMAIL PROTECTED]>,
JPeschel <[EMAIL PROTECTED]> wrote:
 
> [EMAIL PROTECTED]  (Paul Schlyter) writes:
> 
>> The only known way to crack single DES is by brute force: if you have
>> one cleartext-cryptotext pair, try all possible keys until you
>> encounter the correct key.  
> 
> It's not always necessary for an attacker to possess one cleartext-
> cryptotext pair.
 
OK, but then you must have some other way to determine whether
you've obtained the correct cleartext or not.
 
-- 
================================================================
Paul Schlyter,  Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40,  S-114 38 Stockholm,  SWEDEN
e-mail:  [EMAIL PROTECTED]    [EMAIL PROTECTED]   [EMAIL PROTECTED]
WWW:     http://hotel04.ausys.se/pausch    http://welcome.to/pausch

------------------------------


** 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
******************************

Reply via email to