Cryptography-Digest Digest #594, Volume #14 Tue, 12 Jun 01 09:13:01 EDT
Contents:
Re: The 94 cycle 64-bit block cipher :-) (Phil Carmody)
Re: One last bijection question (Nicol So)
Re: One last bijection question ([EMAIL PROTECTED])
Re: One last bijection question (Nicol So)
Re: IV ([EMAIL PROTECTED])
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY (Tim Tyler)
Re: One last bijection question ([EMAIL PROTECTED])
Re: BigNum Question (Tim Tyler)
Re: Any Informed Opinions? ("Dirk Bruere")
Re: IV (SCOTT19U.ZIP_GUY)
Re: 3 trip encryption Exchange (SCOTT19U.ZIP_GUY)
Re: help non-elephant encryption-URL.. (Jeffrey Williams)
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY LONG (Tim
Tyler)
----------------------------------------------------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: The 94 cycle 64-bit block cipher :-)
Date: Tue, 12 Jun 2001 10:13:07 GMT
Tom St Denis wrote:
> Just for fun. (Hey if this works it could be the fastest, simplest block
> cipher).
>
> I used the quadratic function x(2x + 1) modulo 2^32 as the round function.
> It has one nasty differential which is a difference in the high bit goes to
> a difference in the high bit with a prob of 1. The rest of the
> differentials are fairly low bounded by as far as I can tell 2^-16. (I'm
> extrapolating from the case of W=8 where the highest is 16/256. Since we
> are four times bigger we get (16/256)^4 = 65536/2^32.
>
> To avoid this nasty one I used a cyclic rotate left by five bits. Now the
> trail has a much lower probability (from the W=8 case it's zero).
>
> So we get two rounds for free (first and last). Given 6 rounds we have a
> bounded prob of (2^-16)^6 = 2^-96 which means most likely differential
> analysis won't break the cipher with eight rounds.
>
> Of course take heed and remember this is a toy cipher design. It's still
> fairly neat that 8 rounds will run in 94 cycles (11.75 cycles per byte). I
> want to see about mixing in a PHT with two quadratics.... :-)
Sounds interesting, even if it doesn't have the strength that others
have.
You often post your stories here, but I rarely see you post code. As
someone near the bottom of the learning curve of crypto (I understand
pure maths, just not how to apply it), maybe you'd like to post your
code for encrypt and decrypt using the above algorithm, so I can get a
feel for how it works (how do you decrypt??)
Your above round function takes 0->0, for reference, which seems less
than optimal.
Phil
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: One last bijection question
Date: Tue, 12 Jun 2001 06:16:57 -0400
Reply-To: see.signature
Mark Wooding wrote:
>
> Nicol So <[EMAIL PROTECTED]> wrote:
>
> > A comment on the terminology: the range of a function f is the image of
> > the domain under f. The codomain of a function is a (not necessarily
> > proper) superset of its range.
>
> This isn't the terminology I'm familiar with. I've always used the
> terms `range' and `image' to mean what you're calling the `codomain' and
> `range' respectively. I think these names were standard in the UK when
> I learned this stuff.
I've done a little digging. Apparently both conventions are used even in
the UK (based on the UK academic sites I've visited).
--
Nicol So, CISSP
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
Subject: Re: One last bijection question
From: [EMAIL PROTECTED]
Date: 12 Jun 2001 06:37:42 -0400
"Douglas A. Gwyn" <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
> > Note that the range is uniquely determined, having specified f().
>
> Well, no, it is the image of the domain and therefore depends on
> the domain. You probably assumed that a function is packaged with
> a specific domain, but there s no logical necessity for that.
If you haven't specified the domain, you haven't specified f. One may
restrict f to smaller domains, or extend f to larger domains--but having
picked, the range is fixed.
Len.
--
Negotiating with one's self seldom produces a barroom brawl.
-- Warren Buffett, 1985
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: One last bijection question
Date: Tue, 12 Jun 2001 06:38:33 -0400
Reply-To: see.signature
"Douglas A. Gwyn" wrote:
>
> [EMAIL PROTECTED] wrote:
> > Note that the range is uniquely determined, having specified f().
>
> ... You probably assumed that a function is packaged with
> a specific domain, but there s no logical necessity for that.
In most of the formal definitions of function I've seen, especially
those in more recent publications, the domain and codomain are indeed
part of the specification of a function. Based on that viewpoint, a
function and a restriction of it are distinct functions. Not only that,
two functions are considered distinct if they have different codomains,
even if they are otherwise identical.
I don't know if there's a "logical necessity" for defining the concept
that way, but I think it is more convenient to include the domain and
codomain in the specification when you're discussing classes of
functions.
--
Nicol So, CISSP
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
Subject: Re: IV
From: [EMAIL PROTECTED]
Date: 12 Jun 2001 06:53:26 -0400
[EMAIL PROTECTED] (Mark Currie) writes:
>
> Sorry, may have missed a discussion on this, but how does CTR compare
> with CBC from a security perspective ?
Schneier compares CTR mode with OFB mode, not with CBC mode. In fact he
lists it as a variant, as ``OFC/counter mode''. Both counter mode and
output feedback mode are used to generate a key stream--i.e., to use a
block cipher as a synchronous stream cipher.
I'm not entirely sure what you mean by ``security perspective''. An error
in the ciphertext creates a corresponding error in the plaintext in CTR
mode, so if the plaintext is known it can be altered by a middleman. Which
means you need some sort of signature or checksum in CTR mode.
And the sequence of counter values should be considered ``well known''.
So the keystream is generated from a known-plaintext, which may aid
cryptanalysis if the underlying block cipher is vulnerable to that.
And just like OTP, if the keystream is reused then both messages are
compromized; they can be XORed to cancel out the key. But that's true
in general for synchronous stream ciphers.
Len.
--
It's always difficult to imagine the effects of a free market when you've
never tried one.
-- Dan Bernstein
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Reply-To: [EMAIL PROTECTED]
Date: Tue, 12 Jun 2001 10:30:43 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: John Savard wrote:
:> It is not surprising, however, that today cryptography is concerned
:> mainly with an area about which Shannon said little, other than to
:> give it a name: the work factor. Particularly as the extreme utility
:> (and practicality, and convenience) of the 'public-key' methods has
:> made them central to most modern employment of cryptographic
:> techniques, despite the fact that their security, in the
:> information-theoretic sense, is precisely nil.
: But, if something that is practically secure is of
: precisely nil security in the information-theoretical
: sense, that means a big contradiction to intuition/
: common-sense, isn't it? How could the theory nonetheless
: gain acceptance?
All the information necessary to read a public key message
resides in a combination of the message and the public key - and
both should be considered to be available to the attacker.
If only he could factor (or whatever) the public key he would
be able to read the message. He has all the information necessary
to do this at his disposal - but alas, the task takes a lot of effort
to perform.
The "information-theoretic" security of such a system can
usefully be though of as being nil.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
Subject: Re: One last bijection question
From: [EMAIL PROTECTED]
Date: 12 Jun 2001 07:15:54 -0400
Nicol So <[EMAIL PROTECTED]> writes:
>
> In most of the formal definitions of function I've seen, especially
> those in more recent publications, the domain and codomain are indeed
> part of the specification of a function. Based on that viewpoint, a
> function and a restriction of it are distinct functions.
Right!
> Not only that, two functions are considered distinct if they have
> different codomains, even if they are otherwise identical.
True. However, enlarging the codomain is often done quite casually,
without a feeling that we're ``changing the function''. Shrinking the
codomain almost is, but it's usually necessary to prove that the new
codomain still contains the range.
On the other hand, changing the domain emphatically changes the
function. But in this case, enlarging the domain takes more work,
because the extension must be specified. Restricting the domain is of
course trivial.
Len.
--
> My name is MiStReSS DiVA...and I am a hackess...
Who said what now? A hackess? Is that some sort of delicious pastry
treat?
-- Phrack Magazine
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: BigNum Question
Reply-To: [EMAIL PROTECTED]
Date: Tue, 12 Jun 2001 11:03:46 GMT
Harris Georgiou <[EMAIL PROTECTED]> wrote:
: Ο Tim Tyler <[EMAIL PROTECTED]> έγραψε στο μήνυμα συζήτησης:
:> OS >= 9 Java: http://www.apple.com/java/
:> OS X Java: http://www.apple.com/macosx/java2.html
:>
:> The source code for BigInteger and BigDecimal is available.
: The big number packages in JDK work quite well, they even have embedded
: functions for most cryptosystem implementations (like secure random prime
: number generator, modulo exponetials, etc) - I have actually implemented the
: basic RSA encryption from scratch in less than 100 lines of code. The only
: problem is that Java is slow and encryption using Java is even slower.
Not my experience - Java positively whips along these days. I'm not
running it under MacOS, mind you - though I've seen reasonable speeds
there as well.
If there's a problem with Java's cryptography stuff, it seems to be that
these classes are immutable, so there's no way of deleting objects - you
can only null them, and wait for the garbage collector to clean
up afterwards.
This approach is not really acceptable for security-sensitive applications
that need to remove all traces of a transaction after it has occurred.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Dirk Bruere" <[EMAIL PROTECTED]>
Subject: Re: Any Informed Opinions?
Date: Tue, 12 Jun 2001 13:06:51 +0100
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Dirk Bruere wrote:
> > The best that can be said (AFAIK) is that something as big as
buckeyballs
> > can be put into a superposition without any kind of 'self measurement'
> > occuring, but mice can't (probably).
>
> That's looking at it in an unproductive manner. It is not the
> phenomenon of life that is involved, it's the projective operation
> no matter how caused. A randomly chosen large system is very
> likely to disrupt coherence, that's all. If you check some of
> the recent expositions of entanglement, it should become clearer.
There are hundreds of expositions concerning entanglement and measurement,
and dozens of theories about how big a mass can be put into such a state and
for how long. Nobody knows what the answer is because only limted
experiments have been done. C60 is, AFAIK, the biggest item to date.
As for life being involved, that may be relevent as it is an information
processing system, although virii are pretty borderline. That's why I
thought it would be interesting if such could be put into a superposition
long enough for them to change state. Of course, if it turns out there is no
size limit, and standard QM does not suggest there is, then one could
theoretically put a cat or a person into such a state, which is why
Schrodinger and Wigner disussed such gedanken experiments.
Dirk
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: IV
Date: 12 Jun 2001 11:56:06 GMT
[EMAIL PROTECTED] wrote in <[EMAIL PROTECTED]>:
>I'm not entirely sure what you mean by ``security perspective''. An error
>in the ciphertext creates a corresponding error in the plaintext in CTR
>mode, so if the plaintext is known it can be altered by a middleman. Which
>means you need some sort of signature or checksum in CTR mode.
>
This means one of the so called advantages of CTR. Will cause problems.
Since you can use CTE to Decrypt portions of a message. IF one used
it in that way you need some sort of checksum or signature for that
small portion to protect one self agaisnt being altered by a middle
man.
>And the sequence of counter values should be considered ``well known''.
>So the keystream is generated from a known-plaintext, which may aid
>cryptanalysis if the underlying block cipher is vulnerable to that.
>
Thats part of the proplen with CTR. How can one prove its not
vulnerable to the specaul sequences. Just becasue it may not be
in the open literature how to take advantage of such "well known"
sequentual inputs does not mean such an attack can't exist.
>And just like OTP, if the keystream is reused then both messages are
>compromized; they can be XORed to cancel out the key. But that's true
>in general for synchronous stream ciphers.
>
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: 3 trip encryption Exchange
Date: 12 Jun 2001 12:08:32 GMT
[EMAIL PROTECTED] (Neil Couture) wrote in
<9g4ain$1hph$[EMAIL PROTECTED]>:
>The algorithms presented by Tom is an implementation of this three-pass
>Shamir PROTOCOL. It is named Massey-Omura cryptosystem where both party
>must have agreed on the value of p- which is not a big issue. The
>three-pass protocol of Shamir only requires ciphers algorithms that can
>be applied to a message in either order ( encryption and decryption ).
>
>
>Formaly:
>
>A & -A and B & -B are encrypting/decrypting primitive related to a
>particular algorithm ( could be private key or public key algorithm )
>and M is the message to send from a to b.
>
> step: 3 2 1
>M = -B [ -A [ B [ A [ M ] ] ] ]
>
>
>( taken from John Savard site!::
>http://home.ecn.ab.ca/~jsavard/crypto/pk0504.htm )::
>More generally speaking we do:
>-A wishes to send a message to B. So, A takes the message, and enciphers
>it in cipher A, sending the result to B.
>
>-B enciphers it in cipher B, sending it back.
>
>-A can still decipher in cipher A, and does so, leaving behind the
>message only enciphered in cipher B. This is sent back to B.
>
>-B reads the message, since it's only enciphered in his cipher.
>
>
>>
>> Thanks for the reply. Is this an encryption protocol that cannot be
>> cracked? If it was cracked, by whom and when
>>
>
>
>The security of the Massey-Omura cryptosystem is based on the Discret
>Logarithms problems ( DL ). So it shall be secure for a bit... But
>other implementation might suffer from a lack
>of security by using improper protocol or worse by IMPROPERLY using
>algorithms.
>( again John Savard site, if you want an attack of this protocol using
>XOR cypher
>is presented )
>
>
>Neil
>
I am surprise John got this one correct. Just as there is a lot
of bad information abut OTP's. There use to be a lot of misinformation
spread about the use of this protcol. Back when Preston's site for
example had it all wrong. Glad to see this seems to be getting
cleared up. Know if John could clear up the confustion of OTP's
and how to use them for perfect security with a set of input
messages of varible lengths it would help more new people in crypto.
What ever happen to Preston anyway?
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: Jeffrey Williams <[EMAIL PROTECTED]>
Subject: Re: help non-elephant encryption-URL..
Date: Tue, 12 Jun 2001 07:26:20 -0500
By whose definition? The only relevant text I have at work states that they
should be at least one-to-one, which certainly implies that they could be
one-to-one and onto. The same text states that they must be computationally
infeasable to reverse. I always understood that it was that property that made
them one-way functions.
Jeff
Tom St Denis wrote:
<snip>
> Is not possible. One way functions must have collisions by definition.
> Therefore it can't be perfect. (Otherwise it can't be one-way).
<snip>
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
LONG
Reply-To: [EMAIL PROTECTED]
Date: Tue, 12 Jun 2001 11:49:39 GMT
Dennis Ritchie <[EMAIL PROTECTED]> wrote or quoted:
>Tim Tyler wrote:
> > It appears that Shannon's work didn't address the case of finite
> > strings being encrypted with an OTP.
> >
> > His reference to an OTP was in the context of infinite messages.
>
> On the contrary, it's hard to find anything in the Secrecy Systems
> paper referring to infinite messages.
The section I was referring to was:
``The situation is somewhat more complicated if the number of messages
is infinite. Suppose, for example, that they are generated as infinite
sequences of letters by a suitable Markoff process. It is clear that
no finite key will give perfect secrecy. We suppose, then, that the
key source generates key in the same manner, that is, as an infinite
sequence of symbols. Suppose further that only a certain length of
key $L_K$ is needed to encipher and decipher a length $L_M$ of message.
Let the logarithm of the number of letters in the message alphabet be
$R_M$ and that for the key alphabet be $R_K$. Then, from the finite
case, it is evident that perfect secrecy requires [...]
This type of perfect secrecy is realized by the Vernam system.''
This considers an infinite number of infinite messages.
It is the only concrete referece to an OTP from Shannon
that has emerged to date in the context of his discussion
of perfect secrecy.
> "Perfect secrecy" is defined by requiring of a system that
> after a cryptogram is intercepted by the enemy the a posteriori
> probabilities of this cryptogram representing various
> messages be identically the same as the a priori probabilities
> if the same messages before the interception. It is shown that
> perfect secrecy is possible, but requires, if the number of
> messages is finite, the same number of possible keys. If
> the message is thought of as being constantly generated at
> a 'rate' R (to be defined later), key must be generated
> at the same or greater rate."
No mention of an OTP there. An OTP *can't* be used there -
if the messages have varying lengths.
> Let us suppose the possible messages are finite in number
> M1, ..., Mn and that these are enciphered into the possible
> cryptgrams E1, ... En by E = TiM ...."
> [Ti is the transformation performed on the i-th message]
No mention of an OTP there either. Again, an OTP *can't* be used
there - if the messages have varying lengths.
> It is of course true that the paper does not take great account of enemy
> observation of message length and whether this supplies much
> information; as others have remarked, this is the realm of traffic
> analysis [...]
I consider the realm of obtaining information about the plaintext
from the cyphertext itself to be the domain of cryptanalysis.
That /sometimes/ message lengths can convey useful information
in the clear (and can thus be used for traffic analysis) does
not invalidate this.
The length of the plaintext can be obscured by cryptography
like every other aspect of it. It is quite possible for
cryptanalysis (rather than traffic analysis) to be the only
method of getting anything useful out of it.
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
