Cryptography-Digest Digest #869, Volume #11 Sat, 27 May 00 06:13:01 EDT
Contents:
Re: Another sci.crypt Cipher ([EMAIL PROTECTED])
Re: Matrix key distribution? (Benjamin Goldberg)
Re: Encryption within newsgroup postings ("Douglas A. Gwyn")
Re: bamburismus ("Douglas A. Gwyn")
Re: Matrix key distribution? ("Douglas A. Gwyn")
Re: list of prime numbers (Daniel)
Re: PGP wipe how good is it versus hardware recovery of HD? (JohnNY)
Re: list of prime numbers (Daniel)
Re: A Family of Algorithms, Base78Ct (wtshaw)
Re: Encryption within newsgroup postings (wtshaw)
Re: Is OTP unbreakable? (Greg)
Re: RSA/PK Question (Bob Silverman)
Re: A Family of Algorithms, Base78Ct (Mok-Kong Shen)
Re: RSA/PK Question (David Blackman)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Another sci.crypt Cipher
Date: Sat, 27 May 2000 05:50:26 GMT
In article <[EMAIL PROTECTED]>,
tomstd <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> (Mark Wooding) wrote:
...
A nice attack. I had trouble reproducing it, though.
...
> If I were to implement this on reduce rounds (for the fun of
> it), would I just take a plaintext (A,B) and (A,B xor 00010000)
> and look for the output difference of (A xor 00030000, B) after
> 3 or 4 rounds? I am not clear on this part.
>
> BTWx2 Thanks for the info, I really want to learn from this.
> BTWx3 I designed this cipher so I could break it. So I am not
> disappointed it was broken, just that I didn't do it first.
>
> Tom
Tom,
Here is even a better attack, I believe. The code is at the end, make
sure you reduce the rounds to 6!
The differential is 00 00 00 0c -> 00 00 00 0c 4/256 for box 0.
I noticed that all of the entries in sbox 0 ended in 0,4,8 or C. I
though it might be possible to get a truncated differential of the
form 00 00 00 xx -> 00 00 00 xx. Sure enough 0x0c does just that.
The or'ing in of the other words does not seem to affect the
differential. I am a bit confused by that.
I believe the differential for 16 rounds will be 2^-60. A 2R or 3R
attack could probably be mounted requiring 2^48 plain/cipher text.
R p1 p0
0 0 c prob = 1
1 c 0 2^-6
2 c c 2^-6
3 0 c 1
4 c 0 2^-6
5 c c 2^-6
6 0 c 1
7 c 0 2^-6
8 c c 2^-6
9 0 c 1
A c 0 2^-6
B c c 2^-6
C 0 c 1
D c 0 2^-6
E c c 2^-6
F 0 c 1
c 0 cipher text
#include <stdio.h>
unsigned char a[256][16];
int main(void)
{
unsigned long k;
int i,j;
int max;
int maxI;
int maxJ;
unsigned long count;
unsigned long key[4];
srand(234);
count = 0;
// just some random values
key[0] = 0x324803B4;
key[1] = 0x124891AC;
key[2] = 0x142381CB;
key[3] = 0xACEFBD01;
while(1)
{
unsigned long p[2],p1[2];
unsigned long c,c1;
unsigned long hold;
p[0] = rand(); // I am using an old 16 bit compiler
p[0] <<=16;
p[0] = p[0] |(unsigned long)rand();
p1[0] = p[0]^0x0000000CL;
if((count%65536) == 0)
{
hold = rand();
hold <<=16;
hold = hold |(unsigned long)rand();
srand(rand()); // just to avoid a loop
}
p[1] = hold;
p1[1] = p[1];
tc1_encrypt(p, key);
tc1_encrypt(p1, key);
// for the output of round 6
if(((p[0]^p1[0]) == 0x0000000CL)
&& ((p[1]^p1[1]) == 0x00000000L))
a[0][0]++; // just a counter
count++;
}
/*
p1 p0
0 0 c
1 c 0
2 c c
3 0 c
4 c 0
5 c c
6 0 c
7 c 0
8 c c
*/
}
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Matrix key distribution?
Date: Sat, 27 May 2000 06:09:14 GMT
Michael Brown wrote:
>
> Mark Wooding <[EMAIL PROTECTED]> wrote in article >
>news:[EMAIL PROTECTED]...
> > Am I missing something? Can you not just use the fact that you
> > know kf + lh and m(kf + lh), both in CB above, to find m?
> Absoloutely correct. Stupid me. Sorry for bothering you.
>
Perhaps this seems like a silly question, but what if matrix C isn't in
any special format, but whose only property is that it's non-invertable?
> Are there any other matrix encryption things around?
Encryption things? Sort of... Someone recently came up with a cipher
called "Storin" and posted it to this NG, and I recall someone
mentioning
something called "Hill's algorithm," but those are ciphers, not key
exchange algorithms.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Encryption within newsgroup postings
Date: Sat, 27 May 2000 05:15:49 GMT
Anton Stiglic wrote:
> Now is that realy english?
Now it is..
Seriously, although the original "ciphertext" was probably
gibberish and not really enciphered natural-language text,
one does need to be careful when deciding whether or not a
putative plaintext sample is consistent with the assumed
natural language. Although the combination QZYXCB has never
before been seen in English text, that doesn't mean that the
best estimate of its probability is zero. (In fact, now it
*has* occurred in English text! Bother! For the purposes
of this discussion, choose a similar string that hasn't yet
appeared.) If one mistakenly attributes probability 0 to
the event, then its occurrence in putative plaintext causes
one to decide *with certainty* that it cannot really be
plaintext, which is overly pessimistic. Somewhere in MilCryp
(preparation of digraph tables, as I recall) the authors
assign "one-half of an occurrence" to any combination that
was not seen in the sample, in a simplistic effort to avoid
this problem. The question of what the best assignment of
probability is for an as-yet unseen event is an interesting
puzzle; around 1940 Alan Turing came up with a method at GCCS
that was classified for a long time, but eventually appeared
in writings by I. J. Good; original open publication was an
article in Biometrika, around 1950 as I recall. (There have
been recent further developments in this area in the open
literature, but I don't have references close at hand.)
If you don't already know a good solution, it may be
instructive to try to figure one out.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: bamburismus
Date: Sat, 27 May 2000 05:49:41 GMT
John Savard wrote:
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
> >Which part?
> That, at (presumably) a specific date in the past, the NSA definitely
> could not crack 3DES.
At some unspecified time in the past nobody could crack 3DES,
so far as I know, but how long ago, and how complete is my
knowledge? It is obviously true if you go back far enough,
and anyway it is generally believed that 3DES is uncrackable.
> That, at a specific date in the past, the NSA was in posession of
> theoretical results relevant to the cracking of 3DES ..
You're assuming something that was not implied by what I said.
I suspect they have their own analyses of 3DES's vulnerability,
but if so those have nothing to do with me (in either direction).
> - from which, its capability or otherwise to crack 3DES in the
> present day moves from the realm of a _possibility_ to that of
> (however vaguely estimated) a _probability_.
0.5 plus or minus 0.5? Actually from the work I did, I
think it is a hard problem, and I have no good estimate
for the likelihood that it has been solved by others.
> Those were the things that I would believe to be _considered_
> injudicious by those who are concerned with maintaining security.
I haven't yet received any official complaints.
> As to the question of _genuine_ damage to national security,
> however, I will admit to being unqualified to comment.
I am quite careful not to damage legitimate US national security
interests. If you want, I can put you in touch with the
appropriate people to discuss the matter; send me e-mail. An
open forum like this is not appropriate for such a discussion.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Matrix key distribution?
Date: Sat, 27 May 2000 05:52:23 GMT
Michael Brown wrote:
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote...
> > The problem is that matrix methods are inherently highly linear
> > and thus simple algebraic manipulations can be used to crack them.
> Yeah, that's what I was always seeming to run into. I was hoping that by
> some combination of singular matricies you wouldn't be able to do this.
Basically, all that singularity does is reduce the rank, i.e. it
is still a linear system with a (possibly) lower dimensionality.
------------------------------
From: [EMAIL PROTECTED] (Daniel)
Subject: Re: list of prime numbers
Date: Sat, 27 May 2000 06:32:37 GMT
On Thu, 25 May 2000 21:50:00 GMT, [EMAIL PROTECTED] (Dan Day) wrote:
>Daniel, what were you hoping to do with the list? If you'll
>explain your application, we can help you address your problem
>more directly, since keeping a "list" of primes is likely to
>be a poor way to get the job done, whatever it is.
>
>
Thanks for all the replies.
I'm trying to understand RSA and want to be able to factor a given
'public modulus'. Or try it at least ;-)
If one has a large number (say 150 digits), what are the ways to try
and break this up into its factors? Where does one start? I think
that there can only be a limited list of possible prime numbers which
will actually (when multiplied) come up with the correct public
modulus. Or am I wrong about this? All information is greatly
appreciated.
Thanks.
------------------------------
From: JohnNY <[EMAIL PROTECTED]>
Subject: Re: PGP wipe how good is it versus hardware recovery of HD?
Date: Sat, 27 May 2000 02:40:17 -0400
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] (Guy Macon) wrote:
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] wrote:
>
>>I have a program called shredder which I believes overwrites a file 7
>>times with random data to try and prevent hardware recovery of deleted
>>files aka the story in the WSJ. Does PGP wipe function do this or does
>>it only overwrite once?
>
>If history is a guide, you will now read a claim that single pass
>wipes are perfect. This ignores the possibility that recovery is
>possible and that those who can do the recovery aren't telling.
>There is even the possibility that they hire people to post in
>this newsgroup claims that single pass wipes are perfect...
Does anyone know of any overwritten data that has been recovered? For
instance, any forensic labs that claim they are able to do it or
possibly evidence presented in a court case? I have read theoretical
arguments on how it could be done but have not heard of a documented
case. Just curious and no I am not being paid to post this message :)
Thanks,
John
------------------------------
From: [EMAIL PROTECTED] (Daniel)
Subject: Re: list of prime numbers
Date: Sat, 27 May 2000 06:51:10 GMT
On Thu, 25 May 2000 12:22:02 -0700, tomstd
<[EMAIL PROTECTED]> wrote:
>Try getting the HAC and reading it.
>
>Tom
>
>
Could you explain what the HAC is? What does it stand for?
Where can I find it?
Thanks
Daniel
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: A Family of Algorithms, Base78Ct
Date: Sat, 27 May 2000 00:25:18 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
> 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.
Surely you can add nulls, diverse options, or any other primative
distraction you wish. I have exercised most of these tricks in various
implementations. In a more basic form, base translation algorithms are
adequate for limited use, as it might take more that what is available to
unlock the secrets of a particular set of keys. And, as a pretreatment
for other algorithms, base translation can easily shape data to more
efficient final encryption.
>
> 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
Which can be a good thing. If something like alphabetic output is seen,
base translation would be the last of the list of algorithms to be looked
at. Not leaking true length in a symmetric sense means making plaintext
and ciphertext hard to pair
If increased length is tied with increased security, you pay the freight
for it, which can be worth the price if reasonable. Constant length
require more investment in algorithm than is necessry for results given
conservative freedom to add length. I would not suggest that base
translations are nearly as effective in getting strength this way then the
GVA.
--
If a privacy policy is longer that 250 words, it is already
deceptive; the longer the more deceptive.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Encryption within newsgroup postings
Date: Sat, 27 May 2000 00:32:04 -0600
In article <[EMAIL PROTECTED]>, Anton Stiglic <[EMAIL PROTECTED]> wrote:
> "Douglas A. Gwyn" wrote:
> >
> > Anton Stiglic wrote:
> > > I don't think that there is a two letter word in english
> > > that has the same two letters (in french neither...).
> >
> > My friend the witch doctor,
> > He told me what to do.
> > He said:
> > Oo, ee, oo aa aa,
> > Ting tang, walla walla bing bang.
> > ...
>
>
> Now is that realy english?
>
> Shoubougamo bindong boummmmmmm bang-bang!
>
> :)
Imagine me being picky; you left out a couple of lines from the passage:
> > My friend the witch doctor,
> > He told me what to do.
My friend the witch doctor,
he told me what to say.
> > He said [that]:
> > Oo, ee, oo aa aa,
> > Ting tang, walla walla bing bang.
Oo, ee, oo ah ah,
Ting, tang ting, walla boom bang.
Accuracy counts?
--
If a privacy policy is longer that 250 words, it is already
deceptive; the longer the more deceptive.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?
Date: Sat, 27 May 2000 08:10:29 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Greg wrote:
> > And of course you really don't need any math to state the obvious,
> > now do you?
>
> History has shown that "the obvious" is *especially* in need of
> carefully reasoned proof. Your informal "proof" of OTP security
> is so sloppily phrased that similar "reasoning" could be applied
> to some systems which definitely can be cracked; i.e., it is not
> a valid proof.
>
Okay, I am interested... Give me an example of where the same statement
could be applied to another system that is faulty. I think that the
obviousness comes from the simple design of OTP and that something
more complex could not OBVIOUSLY apply the same proof to, but I could
be wrong. Let me know what other cases would show that I am.
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: RSA/PK Question
Date: Sat, 27 May 2000 08:31:24 GMT
In article <[EMAIL PROTECTED]>,
Jerry Coffin <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
>
> For example, if you want some information to remain secure for at
> least the next 50 years, you'd _better_ not depend on an RSA key of
> 768 bits, even though that's (AFAIK) unbreakable at the present time.
> In 50 years, an average hand-held calculator is likely to have more
> than enough resources to break a 768-bit key.
Typical inane sci.crypt technobabble.
I will give you a hint: Think about the *power* requirements to drive
a processor that fast. Think about the power needed to refresh
a terabyte of memory.....
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A Family of Algorithms, Base78Ct
Date: Sat, 27 May 2000 10:56:38 +0200
wtshaw wrote:
> Surely you can add nulls, diverse options, or any other primative
> distraction you wish. I have exercised most of these tricks in various
> implementations. In a more basic form, base translation algorithms are
> adequate for limited use, as it might take more that what is available to
> unlock the secrets of a particular set of keys. And, as a pretreatment
> for other algorithms, base translation can easily shape data to more
> efficient final encryption.
Certainly you are right in questioning whether it is worthwhile to add
all sorts of bells and whistles. I like nevertheless to indicate that adding
a randomly chosen number is a shifting, i.e. akin to a Vigenere in
principle.
M. K. Shen
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: RSA/PK Question
Date: Sat, 27 May 2000 19:33:33 +1000
Bob Silverman wrote:
>
> In article <[EMAIL PROTECTED]>,
> Jerry Coffin <[EMAIL PROTECTED]> wrote:
> > In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] says...
> >
>
> > For example, if you want some information to remain secure for at
> > least the next 50 years, you'd _better_ not depend on an RSA key of
> > 768 bits, even though that's (AFAIK) unbreakable at the present time.
> > In 50 years, an average hand-held calculator is likely to have more
> > than enough resources to break a 768-bit key.
>
> Typical inane sci.crypt technobabble.
>
> I will give you a hint: Think about the *power* requirements to drive
> a processor that fast. Think about the power needed to refresh
> a terabyte of memory.....
>
> --
> Bob Silverman
> "You can lead a horse's ass to knowledge, but you can't make him think"
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
Jerry seems very sure that either Moore's law is going to hold for
another 50 years, or a major improvement in algorithms will happen.
Bob seems very sure that Moore's law will give up before that, and no
major improvement in algorithms will happen.
Either way is a brave prediction if you're looking that far.
There's no obvious physical reason why you can't fit a terabyte and a
few million MIPS into a handheld and run it off less than a watt.
Currently no-one knows how to do this. Guessing whether it will or will
not be done in 50 years is just guessing.
------------------------------
** 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
******************************
