Cryptography-Digest Digest #866, Volume #11 Fri, 26 May 00 19:13:00 EDT
Contents:
Re: Q: OFB (Bryan Olson)
Re: Another sci.crypt Cipher (tomstd)
Re: Is OTP unbreakable? (Mickey McInnis)
Re: A Family of Algorithms, Base78Ct (Mok-Kong Shen)
Re: Q: OFB (Mok-Kong Shen)
Re: Patent state of Elliptic Curve PK systems? (Paul Rubin)
Re: Patent state of Elliptic Curve PK systems? (Roger Schlafly)
Re: MD5 win32 / linux compatibility ("John E. Kuslich")
Re: OAP-L3: Version 5.x Revealed (Alan Mackenzie)
Re: Reasonably secure OTP passing (Bradley)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Q: OFB
Date: Fri, 26 May 2000 20:07:49 GMT
Mok-Kong Shen wrote:
>
> If one runs a block cipher in n-bit OFB mode with n equal
> to the block size, then one is doing repeated encryption
> of an IV. The output eventually repeats, i.e. the sequence
> of the outputs must have a period.
>
> Question: Are any literatures about the period lengths for some
> well-known ciphers, e.g. DES, available? Thanks.
For a random permutation, the expected cycle length is
2^(n-1) + 1/2. The distribution is notable for its
simplicity: all possible cycle lengths are equally likely.
Well-known symmetric block ciphers are designed to look
like random permutations. If they do the job reasonably
well, then traveling a single cycle given a 64-bit block
is just within tractability. An empirical study of the
cycle length distribution would require many data points
and push the cost to the unfundable.
If a block cipher tended to induce cycles much shorter
than expected from a random permutation, a theoretic or
empirical study might be able to expose the defect. That
would result in people rejecting the cipher, and thus for
all the popular symmetric ciphers the only results we have
are that we cannot tell that their cycles are shorter than
expected from a random permutation.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: Another sci.crypt Cipher
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 26 May 2000 13:15:44 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> The chance of getting these keys is 2^-96 right? Hmm I can
live
>> with that. Think I should include the round counter
>> to 'counter' the weak keys?
>>
>> Thanks for looking at my cipher.
>
>I have a 16-round differential characteristic for your complete
cipher,
>with probability approximately 2^{62.5}.
>
>The characteristic evolves like this:
>
> 0: 00000000 00010000
> 1: 00010000 00000000 (01[1] -> 03[2], p = 4)
> 2: 00000300 00010000 (03[2] -> 01[1], p = 6)
At http://www.tomstdenis.com/tc1_break.c
I tried the two round char (0, 00010000) -> (00010000, 0) ->
(00000300, 00010000) but have yet to see it happend.
Could you please check my test (it's really short) I don't think
I understand how to test it properly.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (Mickey McInnis)
Subject: Re: Is OTP unbreakable?
Date: 26 May 2000 20:24:06 GMT
Reply-To: [EMAIL PROTECTED]
In article <8gmi2g$9mv$[EMAIL PROTECTED]>, Joaquim Southby
<[EMAIL PROTECTED]> writes:
|> In article <8gmfq9$ol4$[EMAIL PROTECTED]> Mickey McInnis,
|> [EMAIL PROTECTED] writes:
|> >One way to exploit this is:
|> >
|> >1) Somehow determine the cleartext for one message or part of a
|> > message . (dumpster diving, find a note that was sent to many
|> > correspondents, one of whom you've corrupted, etc.)
|> >
|> >2) Intercept the ciphertext.
|> >
|> >3) Determine the pad from the cleartext/ciphertext pair.
|> >
|> >4) Now you can encrypt a message of the same length as this one
|> > cleartext and send it to the recipient and it will look as
|> > though it came from the "authorized" sender. If you have a
|> > partial message, you can change that part of the message.
|> >
|> I'm a little confused about your reasoning for item 4. You've recovered
|> plaintext and intercepted the corresponding ciphertext. From these, you
|> have recovered the keystream used for that message.
|>
|> Since the OTP security is based on never using the same portion of
|> keystream twice (hence, "One Time"), how would your new message pass
|> muster if it uses the previously used keystream? Are you assuming that
|> the ciphertext you intercepted did not reach the receiver?
Yes, by "intercept", I meant you receive the original ciphertext and
the receiver you wish to deceive only gets your altered copy. Something
like stealing a physical note or diskette or inserting equipment of your own
in the communications link to filter messages.
--
Mickey McInnis - [EMAIL PROTECTED]
--
All opinions expressed are my own opinions, not my company's opinions.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A Family of Algorithms, Base78Ct
Date: Fri, 26 May 2000 22:49:49 +0200
wtshaw wrote:
> <[EMAIL PROTECTED]> wrote:
> > wtshaw wrote:
> > > The essence of the mathematical relationships, the inequalities in most
> > > cases, is at the heart of the concept. By studying the mathematical
> > > relationships involving an associated set of bases in a given algorithm,
> > > you should come to learn pretty much all that you need. If you have
> > > addition questions, ask.
> >
> > I like to know whether the following correctly captures the essence
> > of your methods:
> >
> > One has a string of digits in a base B1. Break this up into sets of
> > certain fixed size. The digits in each set represent an integer in base
> > B1. Obtain the representation of these integers in base B2. This results
> > in sets of digits in base B2. Do some permutation of the digits in
> > each set. Finally concatenate all to form a string of digits in base B2.
>
> Yes, but you can transpose *digits* in any of the bases, and/or substitute
> in any base. Fore example, base 26 can be an intermediate base, be
> substituted and/or letters tranposed.
>
> With usual base translation, the inequalities mean that there are fewer
> possible different types of groups possible than the ciphertext set might
> indicate. This is where the efficiencies should be considered,
> actual/expected for any specific base change. The higher the efficiency,
> the stronger that stage can be, depending on choice of keys.
You certainly mean when c1 digits in base b1 (range [0, b1^c1-1])
are converted to c2 digits in base b2 (range [0, b2^c2-1]) there is
the range [b1^c1, b2^c2-1] that is not used and thus wasted.
However, there is a way to exploit that for some use, if one wishes.
One could namely add to the converted result a random number in
the range [0, d] with d = b2^c2-b1^c1. The analyst, being without
knowledge of that random number, wouldn't be able to do the back
conversion.
One slight disadvantage of base conversion is that, for example, if
one starts with a bit string and does a sequence of base conversions,
then, if the final string is also represented in bits, there is certain
increase of length. That is, the transformation is not length preserving
in general.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: OFB
Date: Fri, 26 May 2000 22:59:39 +0200
Bryan Olson wrote:
> Mok-Kong Shen wrote:
> >
> > If one runs a block cipher in n-bit OFB mode with n equal
> > to the block size, then one is doing repeated encryption
> > of an IV. The output eventually repeats, i.e. the sequence
> > of the outputs must have a period.
> >
> > Question: Are any literatures about the period lengths for some
> > well-known ciphers, e.g. DES, available? Thanks.
>
> For a random permutation, the expected cycle length is
> 2^(n-1) + 1/2. The distribution is notable for its
> simplicity: all possible cycle lengths are equally likely.
>
> Well-known symmetric block ciphers are designed to look
> like random permutations. If they do the job reasonably
> well, then traveling a single cycle given a 64-bit block
> is just within tractability. An empirical study of the
> cycle length distribution would require many data points
> and push the cost to the unfundable.
>
> If a block cipher tended to induce cycles much shorter
> than expected from a random permutation, a theoretic or
> empirical study might be able to expose the defect. That
> would result in people rejecting the cipher, and thus for
> all the popular symmetric ciphers the only results we have
> are that we cannot tell that their cycles are shorter than
> expected from a random permutation.
However, we ''cannot tell'' not because we have investigated
the issue and found no significantly short cycles but because
we haven't studied that (for whatever reasons) and thus don't
(yet) know. On the other hand, if shorter cycles exist, that means
only that the cipher is less satisfactory in OFB but says nothing
direct about other modes of use, I suppose.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Patent state of Elliptic Curve PK systems?
Date: 26 May 2000 21:31:02 GMT
In article <[EMAIL PROTECTED]>, Roger Schlafly <[EMAIL PROTECTED]> wrote:
>Certicom says it has some patent applications pending, but
>it is hard to see how they will stop anyone. Most people
>get better performance in software with other bases, ie,
>trinomial bases. Or one can use (non-optimal) normal bases.
>Or use prime fields where you have more curves and fewer
>known attacks.
What about the technique of representing the point (x,y) as (x,sgn(y))
in a message, since the rest of y can be computed from x? That's been
given the fancy name "point compression" and I have dim memory of hearing
it was patented. Not being able to use it defeats much of the advantage
of EC :(((.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Patent state of Elliptic Curve PK systems?
Date: Fri, 26 May 2000 14:55:13 -0700
Paul Rubin wrote:
> What about the technique of representing the point (x,y) as (x,sgn(y))
> in a message, since the rest of y can be computed from x? That's been
> given the fancy name "point compression" and I have dim memory of hearing
> it was patented. Not being able to use it defeats much of the advantage
> of EC :(((.
Yes, Certicom said that it has some sort of patent pending related
to point compression. I am doubtful that a patent claiming just
EC point compression will have any significance, even if it gets
the patent, because:
1. It is obvious that a number (in a field) has at most 2
square roots, and the choice can be represented by 1 bit.
2. Certicom put point compression into standards without
telling anyone that it was trying to patent it.
------------------------------
From: "John E. Kuslich" <[EMAIL PROTECTED]>
Subject: Re: MD5 win32 / linux compatibility
Date: Fri, 26 May 2000 15:14:43 -0700
Load the files that give different results into a hex editor and make sure
they are identical. Linux and Windows text files handle new line
differently.
JK http://www.crak.com
Matt Farnell <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Any help would be much appreciated. Here's the problem
>
> I'm using an MD5 c++ class to basically hash files. When using this MD5
code
> I
> get a certain output. I can get this same output by using someone else's
> win32 MD5 command line utility. Therefore this confirms that the result
must
> be correct as two different sources resulted in the same 16 byte output.
>
> The problem I have is when I compile md5 source on linux I get another 16
> byte
> output which does not equal my hash result using windows. I am hashing the
> exact same file. I have also used two different linux MD5 sources that
give
> the same result as each other although still different to the windows
> result. I have also compiled the linux source on both a MIP's and intel
> based system and the results are the same as each other although different
> to windows.
>
> Am I doing or not understanding something fundamentally obvious ?
>
> Regards,
>
> MAtt
>
>
>
>
------------------------------
From: Alan Mackenzie<[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Version 5.x Revealed
Date: Fri, 26 May 2000 19:40:24 +0000
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote
on Fri, 26 May 2000 00:40:17 -0700:
> OAP-L3: Version 5.x Revealed
> (Both OAP-L3 Version 4.x and OAP-L3 Version 5.x are patent pending
> under two separate patent applications.)
[ .... ]
> I am not going to discuss the implications of this new OAP-L3 Version
> 5.x here in this news group at this time.
Oh, what a shame :-)
[ .... ]
> With OAP-L3 Version 5.x, only one person need the full implementation
> with an executable file near 2MB. This person would be responsible for
> creating the data files (the table data files) used in the encryption /
> decryption process.
> The other person only needs to be supplied with software that
> only encrypts and decrypts messages using such a table. I guess
> that this executable file need only be about 50KB or maybe less (for
> a windows executable.)
Why the guess? Surely by now you'll have created this executable and know
exactly how big it is.
[ .... ]
> The software and the data file (a data table) could be kept on a floppy
> disk.
Do you envisage a secure method of distributing the key floppies, other
than by personal contact or by courier service? If not, what are the
advantages of using OAP rather than a one-time pad?
> And when the software is run, it could be read directly from this
> floppy disk and loaded directly into RAM along with the data table.
An _unencrypted_ key on a floppy disk, together with the program that
uses it? Isn't that a _slight_ security hole? Why not encrypt the key
with, say, IDEA, using a pass phrase, much like PGP does?
> Additionally, there would be a few associated pointer / counter files
> that would at most take up another 1000 bytes.
> That's it: software of about 50KB capable of generating about 3E12
> random digits with data files of about 8KB all of which will run
> entirely in RAM (being loaded directly from floppy diskette). Then
> when the encryption or decryption is completed, the only new data
> written to the diskette would be the updated pointer / counter
> files.
> I could incorporate a short routine in the encrypt / decrypt software
> to overwrite RAM to provide about as good of computer hardware
> security imaginable or possible.
Credit card terminals tend to store keys in smart card chips, or split
them between those chips and battery backed ram inside a secure case
designed to erase those keys if the case is tampered with.
> Nothing from the diskette goes to your hard drive ....
assuming you've somehow disabled swapping for the critical RAM regions.
> .... and the RAM is overwritten. Very clean.
> Get an 800MHz or faster Pentium III or AMD Athlon CPU with full speed
> on board cache and I think encryption / decryption could be done quite
> quickly and efficiently.
Just about anything short of long range weather forecasting or running a
Microsoft program could be done "quickly and efficiently" on such a
machine. Most people who'll be wanting to encrypt will have lesser
machines, like 166MHz Pentiums, or 33MHz 486s :-(.
Why the "I think"? What sort of machines have you used for testing, and
how fast did the encryption run on those machines, and how does the speed
compare with other popular encryption programs?
All the best with the patents and the program!
--
Alan Mackenzie (Munich, Germany)
Email: [EMAIL PROTECTED]; to decode, wherever there is a repeated letter
(like "aa"), remove one of them (leaving, say, "a").
------------------------------
From: Bradley <[EMAIL PROTECTED]>
Subject: Re: Reasonably secure OTP passing
Date: Fri, 26 May 2000 18:01:13 -0400
I hope that people are still following this thread that I started a week or
so ago. What I'm really curious about is if an OTP or any very chaotic, if
not proveably random, stream of data can really be confidently decrypted
from a conventional encryption scheme like triple DES or CAST or whatever.
My question is if the general lack of order of this plaintext will prevent
a cryptanalyst from ever really knowing which decryption is correct? If the
*correct* plaintext is itself white noise designed to have little or no
order in it, how will the cryptanalyst ever know if they got the correct
plaintext? If one tries a key which reveals the following plaintext "Give
me the microfilm at the docks at midnight" s/he has a pretty good idea that
the decryption was correct, but if the correct answer is in fact:
"fhbjtOirelkgl;ekg;dlkgSL:Dkgl;fdkgs;dlkgSEd =5469 4 xbdb", won't they
never know if they got it right?
I seem to have left my phd in math in my other pants, but this makes real
intuitive sense to me. If it's true it would seem to make the notion of
electronic distribution of OTPs reasonably safe, possibly improving
consumer grade encryption.
Brad King
[EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
> On another point , OTP is primarily a station to station
> protocol...Has there been any discusion or papers on how to use OTP as a
> multi-station protocol...i.e. if you want to send an encrypted messages
> to different users at different times..how do you synch the OTP key...?
>
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (John Savard) wrote:
> > On Sat, 20 May 2000 14:11:27 GMT, [EMAIL PROTECTED]
> > (John Savard) wrote, in part:
> >
> > >Send, enciphered very thoroughly, a whole bunch of OTPs, each of
> which
> > >comes with an identifying number. Now, the cryptanalyst also has to
> > >determine which OTP one's message is related to...
> >
> > >and if a returning message is sent with a header (all also enciphered
> > >thoroughly in a conventional system) identifying _two_ of the OTPs,
> > >and starting points within them, the cryptanalyst has quite a search
> > >task ahead before even starting the difficult job of analyzing the
> > >correlations between two enciphered texts.
> >
> > I found a spot in my web page where it seemed appropriate to put this
> > notion, explained more fully and with a diagram,
> >
> > http://www.ecn.ab.ca/~jsavard/mi060901.htm
> >
> > which page has been expanded in a couple of other spots as well. I
> > also added a picture of the resistor (and mica capacitor, but I didn't
> > go into that level of detail) color code and the color code of pool
> > balls to the introductory page (to accompany Braille and semaphore)
> >
> > http://www.ecn.ab.ca/~jsavard/intro.htm
> >
> > plus, a new image was added to the page on the fourth dimension. I
> > haven't updated my page in a while, and the last few things done with
> > it were the addition of new additional topics; the encryption part has
> > been static.
> >
> > John Savard (teneerf <-)
> > http://www.ecn.ab.ca/~jsavard/
> >
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
** 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
******************************
