Cryptography-Digest Digest #311, Volume #14 Mon, 7 May 01 19:13:00 EDT
Contents:
Re: n-ary Huffman Template Algorithm (Mok-Kong Shen)
Re: Back to the Drawing Board (John Savard)
Re: linear vs nonlinear (Bryan Olson)
Re: Back to the Drawing Board (Mok-Kong Shen)
Re: Random and not random (James Felling)
Re: Free Triple DES Source code is needed. (Paul Schlyter)
Re: Random and not random (Mok-Kong Shen)
Re: OAP-L3: "The absurd weakness." (James Felling)
Re: Free Triple DES Source code is needed. ("Roger Schlafly")
Re: Random and not random (James Felling)
3-Way (was Re: Tiny s-boxes) (David Hopwood)
Re: LUCIFER (Mitchell Morris)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.math,sci.image.processing,comp.graphics.algorithms
Subject: Re: n-ary Huffman Template Algorithm
Date: Mon, 07 May 2001 21:27:21 +0200
Alex Vinokur wrote:
>
> 2. New URL-address of the 'n-ary Huffman Template Algorithm' page is :
>
> ----------------------------------
> http://visitweb.com/alexvn.huffman
I looked through the posts of discussions in the three
groups archived there. But there is, in my humble
view, barely anything concrete for understanding
'non-numerical cost' (what it is and for what use it
is in practice) or 'n-ary Huffman template'. Its
significance for crypto seems even more unclear.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Back to the Drawing Board
Date: Mon, 07 May 2001 19:42:46 GMT
On Mon, 07 May 2001 21:01:51 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>I am interested to know what you are working on. Unfortunately
>there seems to be not enough standards of terminology in the
>field of coding, so that I failed to find your code in
>the register of a few books that I have. Could you please
>give a bit explanations. Thanks.
In general, the term "m out of n code" means a code where an n-bit
word has m bits in it set to one.
For example, a 3 out of 7 code (with 35 possible values) is used to
transmit 5-level code characters (5-bit characters) with protection
against errors, and a 4 out of 8 code, having 70 possible values, can
be used for 6-bit values.
John Savard
http://home.ecn.ab.ca/~jsavard/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: linear vs nonlinear
Date: Mon, 07 May 2001 13:16:29 -0700
Tom St Denis wrote:
> "Mark Wooding"
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> >
> > > It's my understanding that a function is only nonlinear wrt to a
> particular
> > > group. For example, DES sboxes are nonlinear wrt to GF(2).
> >
> > I think you mean with respect to a particular *ring*. To construct
> > linear functions, we must be able to multiply and add.
>
> Bingo. So a ring is like a field except not all elements are units right?
>
> >
> > > Is it not possible to always define a group in which a function is
> > > linear?
> >
> > Which ring do you think (for example) the Rijndael S-box is linear over?
>
> Um I dunno. My only examples are additions in Zp vs GF(2).
I'm not sure I understand the current question. But suppose
I phrase it as:
Conjecture:
For any bijective function f on a finite set S, there
exists some ring (S, +, *), such that for some u and
v in S,
f(x) = u * x + v
I believe the conjecture is false. I'm not so good with
rings, so if anyone spots an illegal step, please let me
know.
I'll show that the function f on S = {A, B, C, D, E},
f(A)=A, f(B)=B, f(C)=C, f(D)=E, f(E)=D
is not linear in any ring (S, + *). The argument is by
contradiction, so assume for the moment that we have such
a such a ring.
1) f(A) = A = u * A + v
2) f(B) = B = u * B + v
(S, +) is a group, so it has inverses so we can subtract
equation 2 from equation 1.
3) A - B = u * (A - B)
A and B are distinct, so (A - B) is not the additive identity.
Our additive group has prime order, and thus (A-B) must be a
generator. If we add equation 3) to itself,
(A-B) + (A-B) = u * (A-B) + u * (A-B)
(A-B) + (A-B) = u * ((A-B) + (A-B))
By adding equation 3) to itself repeatedly we show,
for all x in S, x = u * x.
Thus our ring is a ring with unity, and the multiplicative
identity is u. We also have,
1) f(A) = A = u * A + v
A = A + v
So v is the additive identity. This leads to a contradiction,
since it implies
f(D) = u * D + v = D
but
f(D) = E
and D is distinct from E.
We could make the question somewhat harder. Suppose we
don't require the set over which we define the ring to be
the domain of the function, but only to contain the domain
of the function.
--Bryan
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Back to the Drawing Board
Date: Mon, 07 May 2001 23:10:50 +0200
John Savard wrote:
>
> In general, the term "m out of n code" means a code where an n-bit
> word has m bits in it set to one.
>
> For example, a 3 out of 7 code (with 35 possible values) is used to
> transmit 5-level code characters (5-bit characters) with protection
> against errors, and a 4 out of 8 code, having 70 possible values, can
> be used for 6-bit values.
Does that have an alternative name in the coding literature
or could you recommend me a good text book where it is
treated? Thanks.
M. K. Shen
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Mon, 07 May 2001 16:22:36 -0500
>
>
> To make things clear for the general readers of this thread,
> I like to point out that the 'currently actual' point under
> debate with Matthew Skala is a weaker form of what I hoped to
> be establishable in the first post that started this debate.
> As explicitly stated there, I am not very sure whether the
> stronger (original) form is without logical flaws. On the
> other hand, I am currently yet fairly convinced that the
> weaker form of the proposition is true. Let me therefore
> once again state that weaker form in detail and give a more
> simple argument than what I have hithertofore put forward
> to support it.
>
> The claim is the following: Given an ideal OTP source that
> deliver m bit segments S1, S2, ... Sm of equal length,
> being each n bits, and given m messages M1, M2, ... Mm
> of the same length, the theoretical perfect security
> is unaffected by any arbitrary chosen permutation of the
> m messages relative to the OTP segments.
>
> Here is my proof: Designate the total of the m segments
> by S, which is large segment from the OTP of m*n bits.
> Let there be two different permutations of the messages
> and denote the concatenation of the messages in the two
> cases by GA and GB, which are also of length M*n bits.
> Now the theory of OTP guarantees that with S I can send
> a (ANY) message of m*n bits with perfect security. Since
> GA is such a message, I have perfect security. Since GB
> is also such a message, I also have perfect security.
>
> M. K. Shen
You are correct in that statement iff the method of choosing that permuatation
is absolutely independent of the OTP bits used. Why is that? Simple. If we use
the contents of Si to determine the permutation that shuffles the
messages/plaintexts, then we have a leak as one of our S's must have a certian
form because the plaintexts are ordered in a specific manner.
Yes this is a small leak, but it destroys the shannon guarantee. If our
permutation is fixed or generated from a seperate chunk of data D, then yes we
still have our security, but we are no more or less secure than if we had simpy
used the set GA.( but we have needed extra effort to get to the same final
point).
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Free Triple DES Source code is needed.
Date: 7 May 2001 22:19:50 +0200
In article <[EMAIL PROTECTED]>, Darren New <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
>> Second what is this C/C++ thing you talk about? It's C *OR* C++ not both.
>
> Since C++ is a superset of C,
No it's not!
The following classical "Hello World" program, for instance, is
acceptable to a C compiler but will be rejected with fatal errors by
a C++ compiler:
main(argc,argv)
char *argv[];
{
printf( "Hello, world\n" );
}
Note the implicit "int" declarations if "argc" and "main()".
In C++ this is illegal even though it's legal in C.
Another example is this struct declaration, which is acceptable
in C but produces a fatal error in C++:
typedef struct mystruct
{
int a;
char b;
} mystruct;
So don't claim C++ is a superset of C -- it's not!
> if you're writing in C++, a library in C or C++ would do. Hence, asking
> for a C/C++ program seems quite reasonable.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Mon, 07 May 2001 23:36:58 +0200
James Felling wrote:
>
> You are correct in that statement iff the method of choosing that permuatation
> is absolutely independent of the OTP bits used. Why is that? Simple. If we use
> the contents of Si to determine the permutation that shuffles the
> messages/plaintexts, then we have a leak as one of our S's must have a certian
> form because the plaintexts are ordered in a specific manner.
> Yes this is a small leak, but it destroys the shannon guarantee. If our
> permutation is fixed or generated from a seperate chunk of data D, then yes we
> still have our security, but we are no more or less secure than if we had simpy
> used the set GA.( but we have needed extra effort to get to the same final
> point).
Couldn't we look at the matter in the following way?
Given m messages, there are m! permutations. Suppose we
send one of these permutation and ask whether the opponent
could crack it? We keep on asking the same question for
all possible permutations? Would there be difference
in the answers?
M. K. Shen
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Crossposted-To: alt.hacker,talk.politics.crypto
Subject: Re: OAP-L3: "The absurd weakness."
Date: Mon, 07 May 2001 17:01:01 -0500
Tom St Denis wrote:
> "Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Tom St Denis wrote:
> > >
> > > "Anthony Stephen Szopa" <[EMAIL PROTECTED]> wrote in message
> > > news:[EMAIL PROTECTED]...
> > > > With your many previous vague and less than precise posts you must
> > > > explain exactly what YOU mean by "leakage."
> > > >
> > > > Not what "leakage" has been defined by others but in your own words
> > > > what you understand this word / concept to mean.
> > > >
> > > > There can be no discussion on what YOU mean by "leakage" unless
> > > > you define it in your own terms because you frequently are ambiguous
> > > > and we cannot assume that you even know what you mean.
> > >
> > > Leakage means what it implies. Every output byte must leak some
> (perhaps
> > > little) info about the input state, this is always going to happen.
> > >
> > > The real question is how much info is leaked, i.e how many bytes (bits,
> > > etc...) are required to learn enough about the internal state.
> > >
> > > Tom
> >
> > I think the place to start in answering this question is to read the
> > Help Files: Theory, Processes, Operation, etc. and the recommended
> > use.
> >
> > Good luck. You'll need it if you think you have a prayer in
> > breaking the OTP files.
>
> Um that's your job not mine. You want to show how secure it is, you should
> come up with attacks on the system.
>
> Tom
Simply put: groups. This means that given any k1 and any k2 there exists a k3
such that F(k1,F(k2,X)) = F(k3,X). This means that aplying that method N times
will give exactly the same level of security as applying it once. ( the proof
is left as an example for the student).
All of the methods I havbe seen are groups or special cases of a more generic
permuting method that is a group, and many of them are groups with other
methods. This means that taking a method and using it over and over again is no
more secure than the generic group operation that it is a special case of.
Worse, some of the methods will comute. This menas F(k1,G(k2,X))=
G(k2,F(k1,X).This is a weakness because it means that if only those two methods
are used in whatever pattern you wish you are no better off than using them (or
their generic equivalent) once.
Some of the methods have fixed points. Data that that method cannot and will
not alter. This means that you must alter the data by annother method. Yes,
every data point can and will be adjusted by some process, but since some
methods have fixed points it will produce a bias in the data at those fixed
points.
I have pointed this out to you in the past, and while I do accept that using
your medhods over and over again you can and will eventually get good data, it
requires more work to get to that point than it would with a conventional
stream cypher.
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: Free Triple DES Source code is needed.
Date: Mon, 07 May 2001 21:19:21 GMT
"Paul Schlyter" <[EMAIL PROTECTED]> wrote
> >> Second what is this C/C++ thing you talk about? It's C *OR* C++ not
both.
> > Since C++ is a superset of C,
> No it's not!
> The following classical "Hello World" program, for instance, is
> acceptable to a C compiler but will be rejected with fatal errors by
> a C++ compiler:
> main(argc,argv)
> char *argv[];
> {
> printf( "Hello, world\n" );
> }
> Note the implicit "int" declarations if "argc" and "main()".
> In C++ this is illegal even though it's legal in C.
You are also using C code that has been out of style for about
15 years. It is deprecated in the C90 and C99 standards.
Here is a nice summary of the incompatibilities between C and C++.
http://www.flash.net/~dtribble/text/cdiffs.htm
But most of these differences are trivial and easily avoided. You'll
find more differences between K&R C and ISO C99.
But back to the original question, it is reasonable to ask for a "C/C++"
library because it is usually easy to put a wrapper on either a C or
a C++ library that makes it usable by either language. Often the
library comes that way.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Mon, 07 May 2001 17:24:16 -0500
Mok-Kong Shen wrote:
> James Felling wrote:
> >
>
> > You are correct in that statement iff the method of choosing that permuatation
> > is absolutely independent of the OTP bits used. Why is that? Simple. If we use
> > the contents of Si to determine the permutation that shuffles the
> > messages/plaintexts, then we have a leak as one of our S's must have a certian
> > form because the plaintexts are ordered in a specific manner.
> > Yes this is a small leak, but it destroys the shannon guarantee. If our
> > permutation is fixed or generated from a seperate chunk of data D, then yes we
> > still have our security, but we are no more or less secure than if we had simpy
> > used the set GA.( but we have needed extra effort to get to the same final
> > point).
>
> Couldn't we look at the matter in the following way?
> Given m messages, there are m! permutations. Suppose we
> send one of these permutation and ask whether the opponent
> could crack it? We keep on asking the same question for
> all possible permutations? Would there be difference
> in the answers?
>
> M. K. Shen
If you assume a fixed permutation( i.e. agreed upon at start) you are neither better
nor worse off than not massaging your data.
------------------------------
Date: Mon, 07 May 2001 23:30:58 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: 3-Way (was Re: Tiny s-boxes)
=====BEGIN PGP SIGNED MESSAGE=====
Tim Tyler wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : Note that "Threeway" aka 3WAY is a design that use a 3x3 sbox in bitslice
> : mode ...
>
> Thanks also to David for directing me towards 3WAY. So far I have not yet
> managed to find out very much about it - besides its use of tiny boxes -
> and the fact that it uses a block size that is divisible by three.
3-Way is described in chapter 7 of
Joan Daemen,
"Cipher and Hash Function Design, Strategies based on linear and
differential cryptanalysis"
Ph.D. Thesis, Katholieke Universiteit Leuven, March 1995.
http://www.esat.kuleuven.ac.be/~cosicart/ps/JD-9500/
It has some key schedule attacks:
John Kelsey, Bruce Schneier, David Wagner,
"Key-Schedule Cryptanalysis of 3-WAY, IDEA, G-DES, RC4, SAFER,
and Triple-DES".
http://www.counterpane.com/key_schedule.html
John Kelsey, Bruce Schneier, David Wagner,
"Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X,
NewDES, RC2, and TEA",
ICICS '97 Proceedings, Springer-Verlag, November 1997.
http://www.counterpane.com/related-key_cryptanalysis.html
but apart from that I'm not aware of any cryptanalysis of it.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOvcYyjkCAxeYt5gVAQHVEwf/ZpKiYP5YRd04m8cJ1NDX9TDX5EojDK2u
fopVQACmdasNMKA4F5RtXvbi2A3RETTu9DpBJq8CfWq5K5Xo6HAKAp1AKbqPQ2wi
96ysVhiqNU5LeevVZ8fEN7c93mM4X0ADT0bwyq0y/EfGMkupcvck2kEGRDSI0FUx
zls54l2NeZX/qGchl/7GIxTgKEDJYSXetSm2MtK7UOQ6500LJ527xdQlqlczizOF
PXGoQOMwbOeSkYSU7R6+Jj7zV4qEHTJrz4esyunE1wgXOWBE+kzXoqckZvdlq41Z
FZwXMajwrFpbUEFI3xY536XTXzFoH3Bo1RTrxcTbrkNTJzkmqla2YA==
=59+D
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Mitchell Morris)
Subject: Re: LUCIFER
Date: 7 May 2001 22:42:23 GMT
"Tom St Denis" <[EMAIL PROTECTED]> wrote in
<TKiJ6.31848$[EMAIL PROTECTED]>:
>
>"Henrick Hellström" <[EMAIL PROTECTED]> wrote in message
>news:9d4cuq$hq4$[EMAIL PROTECTED]...
[snip]
>> Suppose that f(0) = 0, f(1) = 2, f(2) = 3, f(3) = 1. The cyclic
>> decomposition of f would then be (0)(1 2 3). There are two cycles:
>> f(0) = 0 is a fixed point and hence a single element cycle. The other
>> elements form a three element cycle. (1 2 3) means that 1 maps to 2, 2
>> maps to 3 and 3 maps to first first element listed in the cycle, i.e.
>> 1. The cycle (1 2 3) is equivalent to (2 3 1) and (3 1 2). The cycle
>> (1 3 2) is however different, since it is equivalent to f(1) = 3, f(3)
>> = 2, f(2) = 1.
>
>Thanks this helps a lot :-) (nice to see sci.crypt working...) so
>basically all disjoint perms get their own brackets? i.e (x y z)(a b c
>d)(e f) would describe a function of 3+7+2=12 elements and three
>disjoint perms (one of 3 elements, 4 elements and two?)
>
>Tom
>
I don't know if it will be relevant to you (not really grasping how much of
this is trvial to you), but a paper was recently floated across the Python
newsgroup about encryption and groups, and it dealt with this notation in
some detail.
<URL:http://www.inetarena.com/~pdx4d/ocn/crypto0.html>
------------------------------
** 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
******************************
