Cryptography-Digest Digest #6, Volume #12 Sun, 11 Jun 00 18:13:00 EDT
Contents:
Re: Digits of pi in Twofish (Terry Ritter)
Re: PK analogue for passwords ("Joseph Ashwood")
Re: Cryptanalytic gap [was: Re: Some dumb questions] ("Douglas A. Gwyn")
Re: Cryptanalytic gap [was: Re: Some dumb questions] ("Douglas A. Gwyn")
Re: Cipher design a fading field? ("Douglas A. Gwyn")
Re: Large S-Boxes (Mok-Kong Shen)
Re: Large S-Boxes (Mok-Kong Shen)
Re: Random IV Generation (Mok-Kong Shen)
Re: Extending the size of polyalphabetic substitution tables (Mok-Kong Shen)
Re: randomness tests (Mok-Kong Shen)
Re: Cryptanalytic gap [was: Re: Some dumb questions] (David A. Wagner)
Re: Large S-Boxes (tomstd)
Homophones (Mok-Kong Shen)
Re: randomness tests (tomstd)
Re: Large S-Boxes (Mok-Kong Shen)
CRC Programming Help... Please!! (gKw-X)
Re: randomness tests (Mok-Kong Shen)
Re: Large S-Boxes (tomstd)
Re: Chronological Backtracking in Scheme (James Pate Williams, Jr.)
Re: Large S-Boxes (Mok-Kong Shen)
Re: Large S-Boxes (lordcow77)
Re: Cryptanalytic gap [was: Re: Some dumb questions] (JPeschel)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Digits of pi in Twofish
Date: Sun, 11 Jun 2000 17:10:18 GMT
On Sun, 11 Jun 2000 06:18:47 +0000, in <[EMAIL PROTECTED]>, in
sci.crypt Jim Gillogly <[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> On Sun, 11 Jun 2000 04:51:16 +0000, in <[EMAIL PROTECTED]>, in
>> sci.crypt Jim Gillogly <[EMAIL PROTECTED]> wrote:
>>
>> >'Transparency' is a good cryptographic reason. "See, we're using
>> >a pile of bits in here, but there's no back door -- honest. You
>> >can verify for yourself that it's the most obvious pile of bits in
>> >all of mathematics."
>>
>> All of which, of course, says nothing about contrived weakness: One
>> can easily imagine testing a whole raft of mathematical constants to
>> find one with particular weakness properties, and then selecting that
>> constant for the cipher. But that could never happen, could it?
>
>Yes, that could happen, and one should always be checking to see if one
>can spot back doors. However, having it be the <most> obvious constant
>gives that theory less credibility.
Personally, I would say that e would be "the *most* obvious constant."
But whether it is or not does *not* affect the "credibility" of my
argument: I do not have a "theory" that it happened; I do not claim
that it happened. I *do* claim that it *might* have happened, and
that we would not know. So the result is *anything* *but* design
"transparency," yet "transparency" was the reason cited for doing it.
How can that be?
>The DES S-boxes are a case in
>point: we could tell they were clearly non-random before Biham & Shamir
>discovered the reason: that random ones were significantly worse than
>carefully chosen ones. That would have been a deniable way to weaken
>DES (e.g. choose bytes of pi), and they chose not to use it. Before
>B&S's work the regularities, especially in S4, gave rise to much suspicion.
At the risk of beating a dead horse here, that is yet another logic
error: Yes, it is true that DES s-boxes were found to be strengthened
*against* *a* *particular* *attack* *strategy*. It does not follow
that the s-boxes were strengthened in general. It does not follow
that B&S found "the reason" the s-boxes were non-random. Continued
suspicion is very much still warranted.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: PK analogue for passwords
Date: Sun, 11 Jun 2000 12:30:04 -0700
Crossposted-To: comp.security.misc
> This points out though that I was wrong -- SHA-1 instead
of md5. :) I
> think the substitutions at the end remove spaces,
newlines, etc, and
> truncates the result to 8 chars. It looks trivial to get
more characters
> out of it, but since it is SHA-1, the max is probably
around 22
> characters. (Although the inputs to the system are
probably less than 22
> bytes of entropy!)
Just a side note, there's no possible way you're gonna get
22 bytes out of standard SHA-1, SHA-1 is only 20 bytes long.
Joe
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalytic gap [was: Re: Some dumb questions]
Date: Sun, 11 Jun 2000 19:45:06 GMT
John Savard wrote:
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
> >John Savard wrote:
> >> ... Anything that isn't an OTP can, in theory, be solved: ...
> >No.
> If you count brute-force methods, which I was doing in that context,
> I can't immediately see where I've oversimplified.
Here is a simple Casear substitution; solve it:
KWBC
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalytic gap [was: Re: Some dumb questions]
Date: Sun, 11 Jun 2000 19:49:54 GMT
John Savard wrote:
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
> >John Savard wrote:
> >> ... Anything that isn't an OTP can, in theory, be solved: ...
> >No.
> If you count brute-force methods, which I was doing in that context,
> I can't immediately see where I've oversimplified.
Here is a ciphertext resulting from a simple substitution;
tell me how you can determine the corresponding plaintext:
KWVZ
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sun, 11 Jun 2000 19:52:17 GMT
wtshaw wrote:
> In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
> <[EMAIL PROTECTED]> wrote:
> > Cryptosystems form a highly constrained subclass of the class of
> > all possible programs. Consider that the encryption function has
> > to take an arbitrary plaintext and produce a unique corresponding
> > ciphertext that has the property that it will be mapped back to
> > the original plaintext using a fixed decryption function that
> > depends only on the encryption function. Very few programs come
> > anywhere close to meeting this requirement.
> Scientific restraint is based on the natural order of things, not as
> someone wants them to be.
> Yes, very few programs meet the requirement you suggest, which can be,
> together with other aspects, a definite contribution to strength,
> obviously including none designed with prior restraint in mind.
I don't see how that bears on whether cryptanalysis is equivalent
to the halting problem.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: Sun, 11 Jun 2000 22:35:34 +0200
tomstd wrote:
> It has LP and DP tests as well as SAC and BIC. If you can
[snip]
Sorry for my poor knowledge. What abbreviations are DP and
LP? Are SAC and BIC somehow related? Are there good
literatures on BIC? Thanks.
M. K. Shen
>
>
> 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: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: Sun, 11 Jun 2000 22:35:28 +0200
David A Molnar wrote:
> May be worth looking for Stern & Joux _Lattice Basis Reduction : A Toolbox
> for the Cryptanalyst_. It is a different technique than the differential
Could you give the journal and vol. or the URL? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random IV Generation
Date: Sun, 11 Jun 2000 22:36:03 +0200
Terry Ritter wrote:
> Instead of counting in binary sequence, use a finite field.
> Typically, this would be a simple linear feedback shift register
> (lfsr). There is no strength required for the counting sequence; the
> strength improvement comes from not presenting a sequence in which
> only one bit changes fully half the time.
Would a Gray code, which is simple to implement, also be good
at that? Thanks.
M. K.Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Extending the size of polyalphabetic substitution tables
Date: Sun, 11 Jun 2000 22:35:51 +0200
Simon Johnson schrieb:
> Back to your original question. I've been thinking about your
> suggestion; Do you suggest a multidimensional array?
> e.g.
> (output from s-box)=s(x,y)
>
> It will automatically produces collisions. There will be a minimum of 2
> different values for x & y that generate the same output.
>
> Following from this fact, it makes sense that the 2-dimensional array
> can be expressed in terms of a 1-dimensional array. If x, y and the
> output are of the same size, which i will call m, then the s-box would
> be a 2m*m s-box.
>
> Acording to Applied Cryptography V2 (AC2), there is definitly a linear
> relationship if, for an m*n s-box, n>=2^m-m. For this construction, we
> are a long way above this point.
I have not located your citatation. But, if n<n^m-m, that that statement
says anything? (You have: If A then B. But if (not A) then ? )
> e.g. If we have an 8*8*8 s-box that can be expressed like 16*8 s-box
> then we inequality looks like 8/>= 65520. For this reason i am
> confident that such a construction is almost certainly secure against
> linear cryptanalysis.
See above.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: randomness tests
Date: Sun, 11 Jun 2000 22:35:44 +0200
tomstd wrote:
> For any prng I can devise *at least* one test it would fail.
> (obvious give it the same seed). For example if your prng fails
What do youi mean by 'test' above? A test that has some reasonable
statistical foundation, or one that simply outputs 'Fail!'? If the former,
how do you proceed to invent that? Thanks.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Cryptanalytic gap [was: Re: Some dumb questions]
Date: 11 Jun 2000 13:32:05 -0700
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> John Savard wrote:
> > "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
> > >John Savard wrote:
> > >> ... Anything that isn't an OTP can, in theory, be solved: ...
> > >No.
> > If you count brute-force methods, which I was doing in that context,
> > I can't immediately see where I've oversimplified.
>
> Here is a ciphertext resulting from a simple substitution;
> tell me how you can determine the corresponding plaintext:
>
> KWVZ
If we interpret OTP loosely, as meaning "any cipher that is not used past
the unicity distance", then this ciphertext was indeed produced from a
OTP-cipher.
(Why would we want to take such a loose interpretation? Well, if we take
a strict interpretation, there are plenty of counterexamples that are far
more trivial and far less interesting. For example, to encrypt a message
m in GF(2^n), your key will be two values k,k' in GF(2^n), where k != 0,
and the ciphertext will be k*m + k'. This is not strictly speaking a OTP,
but in practice it is just as uninteresting as a OTP, because you can't
use it past the unicity distance, and thus too much key material is needed.)
------------------------------
Subject: Re: Large S-Boxes
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 11 Jun 2000 13:41:07 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> wrote:
>
>
>tomstd wrote:
>
>> It has LP and DP tests as well as SAC and BIC. If you can
>
>[snip]
>
>Sorry for my poor knowledge. What abbreviations are DP and
>LP? Are SAC and BIC somehow related? Are there good
>literatures on BIC? Thanks.
LP is linear probability and DP is difference probability. SAC
and BIC are related that BIC sboxes are also SAC compliant.
SAC is the strict avalanche criterion and BIC is the bit
independence crtierion.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: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Homophones
Date: Sun, 11 Jun 2000 23:10:59 +0200
Homophones appears to be entirely out in modern cryptography.
However, normal texts continue to employ only very limited
characters than the English alphabet, so a space of 70 seems
to be amply sufficient. If each character is stored in a
byte, we can have a homophone mapping of 70 to 256. I suppose
that's enough expansion to effect essential flattening of
frequency distribution of single characters. Since that
transformation is very simple to implement I don't yet fully
understand the disappearance of homopones in current systems.
I mean it could well be a good preprocessing step for modern
ciphers.
Thanks for comments in advance.
M. K. Shen
------------------------------
Subject: Re: randomness tests
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 11 Jun 2000 14:02:18 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> wrote:
>
>
>tomstd wrote:
>
>> For any prng I can devise *at least* one test it would fail.
>> (obvious give it the same seed). For example if your prng
fails
>
>What do youi mean by 'test' above? A test that has some
reasonable
>statistical foundation, or one that simply outputs 'Fail!'? If
the former,
>how do you proceed to invent that? Thanks.
I mean just that. For any PRNG I can devise a test that it
would fail.
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: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: Sun, 11 Jun 2000 23:16:51 +0200
tomstd wrote:
> LP is linear probability and DP is difference probability. SAC
> and BIC are related that BIC sboxes are also SAC compliant.
>
> SAC is the strict avalanche criterion and BIC is the bit
> independence crtierion.
Could you please give good literature pointers (books, journals, URL)
to LP, DP and BIC? Thanks.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (gKw-X)
Subject: CRC Programming Help... Please!!
Reply-To: [EMAIL PROTECTED]
Date: Sun, 11 Jun 2000 21:08:42 GMT
hey guys!
i have some questions regarding crc computation... an answer to any
extent to these qs would be greatly appreciated :)
if one program uses certain variables to create the crcs, and you
can't see what they are directly, is there any way to determine the
variables that go into it by somehow 'reverse engineering' the crc
outputs for different files? (so that you can then support the outputs
of other programs)
does anyone know where i could find some crc code that's flexible
enough to allow you to modify those variables? all the code i've found
is hard to work with in that respect....
does anyone know where i could find a list of the variables that
various programs use to generate crcs, and/or what a 'default' set of
variables are for generating crcs?
any help would be GREATLY appreciated... thanks a ton to those who
actually read this ;)
gKw-X
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: randomness tests
Date: Sun, 11 Jun 2000 23:19:14 +0200
tomstd wrote:
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> >
> >tomstd wrote:
> >
> >> For any prng I can devise *at least* one test it would fail.
> >> (obvious give it the same seed). For example if your prng
> fails
> >
> >What do youi mean by 'test' above? A test that has some
> reasonable
> >statistical foundation, or one that simply outputs 'Fail!'? If
> the former,
> >how do you proceed to invent that? Thanks.
>
> I mean just that. For any PRNG I can devise a test that it
> would fail.
>
Is that kind of arguments appropriate in scientific discourse?
M. K. Shen
------------------------------
Subject: Re: Large S-Boxes
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 11 Jun 2000 14:31:31 -0700
Sure
"The Strict Avalanche Criterion: Spectral Properties of Boolean
Functions and an Extended Definition", Rejane Forre, Crypto 88,
Springer LNCS #403
"The structured design of cryprographically good sboxes",
Carlisle Adams and Stafford Tavares, Journal of Cryptology 1990.
"Nonlinearity crtieria for cryptographic functions" Willi Meier
and Othmar Staffelbach, Eurocrypt '89, Springer LNCS #434
"An expanded set of sbox design criteria based on information
theory and its relation to differntial-like attacks" M.H Dawson
and S.E Tavares, Eurocrypt '91, LNCS #547
"Enumerating Nondegenerate permutations", Luke O'Connor,
Eurocrypt '91, LNCS #547
"Good sboxes are easy to find", Carlisle Adams and Stafford
Tavares, Crypto '87, LNCS #435
"Perfect nonlinear sboxes" Kaisa Nyberg, Eurocrypt '91 LNCS #547
"On the design of sboxes", A.F Webster and S.E Tavares,
Crypto '85, LNCS #218
--
Those are all the papers that Mike Rosing was nice enough to
send me (btw: Mike: if you have anything more along the lines I
would seriously appreciate it, these papers are tremendously
helpful).
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] (James Pate Williams, Jr.)
Subject: Re: Chronological Backtracking in Scheme
Date: Sun, 11 Jun 2000 22:00:44 GMT
On Sun, 11 Jun 2000 06:01:32 GMT, [EMAIL PROTECTED] (James Pate
Williams, Jr.) wrote:
A complete method in another language slight modification of the
previous chronological backtracking algorithm.
/*
Author: James Pate Williams, Jr. (c) 2000
Backtracking algorithm applied to the N-Queens CSP.
Algorithm from _Foundations of Constraint Satisfaction_
by Edward Tsang Chapter 2 page 37. Complete method.
*/
#include <iomanip.h>
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <vector>
using namespace std;
int constraintsViolated(vector<int> &Q) {
int a, b, c = 0, i, j, n;
n = Q.size();
for (i = 0; i < n; i++) {
a = Q[i];
for (j = 0; j < n; j++) {
b = Q[j];
if (i != j && a != - 1 && b != - 1) {
if (a == b) c++;
if (i - j == a - b || i - j == b - a)
c++;
}
}
}
return c;
}
void printSolution(vector<int> &solution) {
char hyphen[256];
int column, i, i4, n = solution.size(), row;
if (n <= 16) {
for (i = 0; i < n; i++) {
i4 = i * 4;
hyphen[i4 + 0] = '-';
hyphen[i4 + 1] = '-';
hyphen[i4 + 2] = '-';
hyphen[i4 + 3] = '-';
}
i4 = i * 4;
hyphen[i4 + 0] = '-';
hyphen[i4 + 1] = '\n';
hyphen[i4 + 2] = '\0';
for (row = 0; row < n; row++) {
column = solution[row];
cout << hyphen;
for (i = 0; i < column; i++)
cout << "| ";
cout << "| Q ";
for (i = column + 1; i < n; i++)
cout << "| ";
cout << '|' << endl;
}
cout << hyphen;
}
else
for (row = 0; row < n; row++)
cout << row << ' ' << solution[row] << endl;
cout << endl;
}
bool Backtrack(vector<int> unlabelled, vector<int> compoundLabel,
vector<int> &solution) {
bool result;
int i, j, v, x;
vector<int> Dx(compoundLabel.size());
if (unlabelled.empty()) {
for (i = 0; i < compoundLabel.size(); i++)
solution[i] = compoundLabel[i];
return true;
}
for (i = 0; i < compoundLabel.size(); i++)
Dx[i] = i;
// pick a random variable from unlabelled array
i = rand() % unlabelled.size();
x = unlabelled[i];
do {
// pick a random value from domain of x
j = rand() % Dx.size();
v = Dx[j];
vector<int>::iterator vIterator = find(Dx.begin(),
Dx.end(), v);
Dx.erase(vIterator);
compoundLabel[x] = v;
if (constraintsViolated(compoundLabel) == 0) {
vIterator = find(unlabelled.begin(),
unlabelled.end(), x);
unlabelled.erase(vIterator);
result = Backtrack(unlabelled, compoundLabel,
solution);
if (result)
printSolution(solution);
unlabelled.push_back(x);
}
else
compoundLabel[x] = - 1;
} while (!Dx.empty());
return false;
}
int main(int argc, char *argv[]) {
if (argc != 2) {
cout << "usage: " << argv[0] << " numberOfQueens" <<
endl;
exit(1);
}
int i, n = atoi(argv[1]);
vector<int> compoundLabel(n, - 1), solution(n, - 1),
unlabelled(n);
for (i = 0; i < n; i++)
unlabelled[i] = i;
srand(time(NULL));
Backtrack(unlabelled, compoundLabel, solution);
return 0;
}
The output of the preceding program for n = 4:
=================
| | | Q | |
=================
| Q | | | |
=================
| | | | Q |
=================
| | Q | | |
=================
=================
| | Q | | |
=================
| | | | Q |
=================
| Q | | | |
=================
| | | Q | |
=================
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: Mon, 12 Jun 2000 00:07:03 +0200
tomstd wrote:
> Sure
[snip]
For saving time of getting books from the library, question: which of
the literatures you gave contain stuffs of BP and DP? Thanks.
M. K. Shen
------------------------------
Subject: Re: Large S-Boxes
From: lordcow77 <[EMAIL PROTECTED]>
Date: Sun, 11 Jun 2000 14:59:44 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> wrote:
>Sorry for my poor knowledge. What abbreviations are DP and
>LP? Are SAC and BIC somehow related? Are there good
>literatures on BIC? Thanks.
This is not meant to be a flame, but you have been an active
participant in this newsgroup for at least the past three years.
Your constant apologies for your "poor knowledge" and your
statements of contrition for your "humble ideas" are starting to
appear repetitious. Combined with your propensity to bring up
ideas (as with the many N-time pad threads, headerless
compression, etc.) that have been discussed extensively already,
I can't help but to question what exactly it is you are
attempting to accomplish.
* 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] (JPeschel)
Subject: Re: Cryptanalytic gap [was: Re: Some dumb questions]
Date: 11 Jun 2000 22:06:53 GMT
[EMAIL PROTECTED] writes:
>Here is a simple Casear substitution; solve it:
>
>KWBC
If it's a Caesar variant, and the sender's language
is English: WINO.
J
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.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
******************************
