Cryptography-Digest Digest #882, Volume #11 Mon, 29 May 00 01:13:01 EDT
Contents:
Evidence Eliminator concerns ("icarus")
Re: encryption without zeros (zapzing)
Help break SNAPPY (tomstd)
Re: Math problem (P=NP) prize and breaking encryption (S. T. L.)
Re: Help break SNAPPY (tomstd)
Smart TC1 optimizations? (tomstd)
Re: Math problem (P=NP) prize and breaking encryption (Scott Contini)
Re: Math problem (P=NP) prize and breaking encryption (Paul Rubin)
Re: Traffic Analysis Capabilities (Rex Stewart)
Re: Math problem (P=NP) prize and breaking encryption (Scott Contini)
Re: encryption without zeros (rick2)
Re: Smart TC1 optimizations? (tomstd)
Re: Math problem (P=NP) prize and breaking encryption (David Blackman)
Re: Math problem (P=NP) prize and breaking encryption (Bill Unruh)
Re: Math problem (P=NP) prize and breaking encryption (David A Molnar)
Re: encryption without zeros (real address at end of post)
Re: No-Key Encryption (wtshaw)
----------------------------------------------------------------------------
From: "icarus" <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy,alt.privacy.anon-server,alt.security.pgp
Subject: Evidence Eliminator concerns
Date: Mon, 29 May 2000 02:23:42 +0100
Reply-To: "icarus" <[EMAIL PROTECTED]>
Hi guys,
I am very concerned about EE. I dont wear a badge. I am a user but not too
naive i hope.
I dont want it to come in on startup and sit there; I want it to come in
when I call it. I have deleted various startup options and it goes away and
comes back two or three times later after a reboot.
I stress that it appears to work but I AM CONCERNED as they are anonymous.
I have sent them an email but i get no reply.
Is it a good tool or A TROJAN ????
EE support, if you have nothing to fear who are you??? I have nothing to
gain, I am a user and not a cop.
regards,
icarus
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
Date: Mon, 29 May 2000 01:28:08 GMT
In article <8gs4kt$8if$[EMAIL PROTECTED]>,
Bryan Olson <[EMAIL PROTECTED]> wrote:
> lordcow77 wrote:
> > Why not? ab//cd0000ef/g -> ab////cd/0/0/0/0ef//g
> >
>
> You didn't explain how to escape out the zeros. The
> escape character followed by a zero byte fails the
> given criteria - it still has zero bytes in it. In
> addition to the escape character, you need to designate
> some character (other than zero or the escape characer)
> to serve as the escaped representation of zero.
>
> I think Guy Macon's comment assumed that the escape
> character by itself would represent zero.
>
In the plantest, let us say there is a
string of n zeros in the unprocessed
ciphertext. Then this is changed to
a strin of 2n zeros. A string of an
od number of zeros, 2n+1 zero to be precise,
would indicate that the unprocessed ciphertext
has a stiring of n zeros followed by
the end of the block. Thus every escape
character tat is actually supposed to get
through is reescaped with itself.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Help break SNAPPY
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 28 May 2000 18:41:36 -0700
I started my cryptanalysis of Snappy.. I began by analyzing
repeated usage of the sbox as in
t = sbox[t]
Or just repeated substitution as it seems the best place to
start. Under this model and 7 substitutions the best diff char
I found was
Best differential: 4160749568
6a, 80, 32, 08, 3a, 30, 82
I.e sbox[x ^ 0x6A] ^ sbox[x] = 0x80 ... and so on. The char has
a probability of 2^-24.05
I am just trying to think how to turn this into an attack on F.
Please help break Snappy (hehehe, it's called snappy and I want
to break it... get it?).
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] (S. T. L.)
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: 29 May 2000 01:46:54 GMT
<<so that being able to answer
the HC problem also answers the factoring problem. >>
I was unaware that factoring had been proven to be NP-complete.
-*---*-------
S.T. "andard Mode" L. ***137*** Join the Minions of Orthodoxy today!
STL's Wickedly Nifty Quotation Collection: http://quote.cjb.net
Currently playing: Half-Life, Commander Keen 4
------------------------------
Subject: Re: Help break SNAPPY
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 28 May 2000 18:44:49 -0700
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
>I started my cryptanalysis of Snappy.. I began by analyzing
>repeated usage of the sbox as in
>
>t = sbox[t]
>
>Or just repeated substitution as it seems the best place to
>start. Under this model and 7 substitutions the best diff char
>I found was
>
>Best differential: 4160749568
>6a, 80, 32, 08, 3a, 30, 82
>
>I.e sbox[x ^ 0x6A] ^ sbox[x] = 0x80 ... and so on. The char has
>a probability of 2^-24.05
Damn arrg....that was suppose to be
Best differential: 2097152
f3, f3, f3, f3, f3, f3, f3
(the other one was for the sbox formed by x(2x+1))
This one has a probability of 2^-35.
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!
------------------------------
Subject: Smart TC1 optimizations?
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 28 May 2000 19:38:20 -0700
Here's my line of thinking on how to optimize TC1 against
Differential Cryptanalysis (as oppose to random permutations).
Basically the goal is to find a bit permutation so that when an
input difference into one of the 8x8 sboxes has an output
difference with high probability, the bits are spread to another
sbox to lower the chance of it spreading.
Hard to explain...
Basically let's say the difference 0xAA->0xBB in one sbox has a
high prob, say around 16/256. We want the output of this entry
to form low probable differences in whatever sboxes it joins up
with. Basically we are looking at two bit differences, so for
example if 0x03->0x05 we want those two bits not to form another
differential (with high prob) in another sbox.
Arrg.. does this even make sense?
Hmm what I want is the highest probability traits go to lower
probability traits.
I am confusing myself.
Please help!
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] (Scott Contini)
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: 29 May 2000 02:48:13 GMT
In article <[EMAIL PROTECTED]>,
S. T. L. <[EMAIL PROTECTED]> wrote:
><<so that being able to answer
>the HC problem also answers the factoring problem. >>
>
>I was unaware that factoring had been proven to be NP-complete.
That's not what he claimed. Re-read his post.
Factoring has not been proven NP-complete (and although I can't
prove it, I will guarantee you that it is not NP-complete!)
Scott
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: 29 May 2000 02:56:36 GMT
In article <[EMAIL PROTECTED]>,
S. T. L. <[EMAIL PROTECTED]> wrote:
><<so that being able to answer
>the HC problem also answers the factoring problem. >>
>
>I was unaware that factoring had been proven to be NP-complete.
Non sequitur. Factoring is in NP and therefore you can reduce it to
any NP-hard problem, including HC.
Factoring is not known to be NP-hard, if that's what you're thinking.
That being able to factor isn't known to mean being able to solve HC.
But HC is NP-hard. That means being able to solve HC means you can
factor.
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: Traffic Analysis Capabilities
Date: Mon, 29 May 2000 03:00:53 GMT
Hmmmm,
"If you have nothing to hide you've probably wasted your life anyway."
I like that. Makes a good tagline. A single line encapsulization of
what Phil Zimmerman said.
Would you like it attributed to you? (also, this is a good time for
re-wording if you don't like the way I captured it :-)
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
In article <[EMAIL PROTECTED]>,
"Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote:
> Guy Macon wrote:
>
> > ... and a life that is an open book with nothing to hide.
>
> The best kind of victim. What the hell, if you have nothing to hide
you've
> probably wasted your life anyway. ;-)
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: 29 May 2000 03:20:51 GMT
In article <8gsm94$t8n$[EMAIL PROTECTED]>,
Paul Rubin <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>,
>S. T. L. <[EMAIL PROTECTED]> wrote:
>><<so that being able to answer
>>the HC problem also answers the factoring problem. >>
>>
>>I was unaware that factoring had been proven to be NP-complete.
>
>Non sequitur. Factoring is in NP and therefore you can reduce it to
>any NP-hard problem, including HC.
>
>Factoring is not known to be NP-hard, if that's what you're thinking.
>That being able to factor isn't known to mean being able to solve HC.
>But HC is NP-hard. That means being able to solve HC means you can
>factor.
Here's my 2 cents:
Factoring is certainly not NP-complete (though a proof of this
does not exist). We can factor in sub-exponential time, but the
fastest algorithms for solving general NP-complete problems take
exponential time.
Scott
------------------------------
From: rick2 <[EMAIL PROTECTED]>
Subject: Re: encryption without zeros
Date: Mon, 29 May 2000 03:25:45 GMT
In article <[EMAIL PROTECTED]>, lcs Mixmaster
Remailer <[EMAIL PROTECTED]> wrote:
> Rick - You could use a regular encryption function like triple DES,
> but if you get an output block which has a zero byte in it, run that
> block through the encryption function again, and repeat until you
> don't get any zeros.
>
> DES uses 64 bit (8 byte) data, so the chances of getting a block with a
> zero is 8/256 or 1/32, so you won't have to repeat the iteration very
> often, and almost never have to do it twice.
>
> To decrypt, do the same thing: decrypt the data block, and if it comes
> out with a zero, decrypt it again. This assumes your input doesn't
> have any zero bytes either, so that the decryption can recognize when
> it is through.
Excellent idea! I think I would rather give up a bit of time and
battery to keep memory expansion to a minimum. Your idea provides
a way to get zero memory wastage, with relatively little cpu
penalty.
Thanks!
Rick
------------------------------
Subject: Re: Smart TC1 optimizations?
From: tomstd <[EMAIL PROTECTED]>
Date: Sun, 28 May 2000 20:27:34 -0700
In article <[EMAIL PROTECTED]>, tomstd
<[EMAIL PROTECTED]> wrote:
>Here's my line of thinking on how to optimize TC1 against
>Differential Cryptanalysis (as oppose to random permutations).
>
>Basically the goal is to find a bit permutation so that when an
>input difference into one of the 8x8 sboxes has an output
>difference with high probability, the bits are spread to another
>sbox to lower the chance of it spreading.
>
>Hard to explain...
>
>Basically let's say the difference 0xAA->0xBB in one sbox has a
>high prob, say around 16/256. We want the output of this entry
>to form low probable differences in whatever sboxes it joins up
>with. Basically we are looking at two bit differences, so for
>example if 0x03->0x05 we want those two bits not to form another
>differential (with high prob) in another sbox.
>
>Arrg.. does this even make sense?
>
>Hmm what I want is the highest probability traits go to lower
>probability traits.
>
>I am confusing myself.
>
>Please help!
I still need help but this may help clear things up
1: 00000019 00000000 (19[0] -> 01[3], p = 4/256)
2: 01000000 00000019 (01[3] -> 04[0], p = 4/256)
3: 0000001d 01000000 (1d[0] -> 01[3], p = 6/256)
Was taken from Mark's program. As you can see a p=1/64 goes to
another p=1/64 and onto a p=6/256. What I want is p=>2/256 to
move to a lower p=<5/256 value, and to avoid anything going
upwards for example p=<5/256 to p=>5/256.
If my bit perm does this it should be resistant to differential
cryptanalysis right?
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: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: Mon, 29 May 2000 14:00:36 +1000
Scott Contini wrote:
>
> Here's my 2 cents:
>
> Factoring is certainly not NP-complete (though a proof of this
> does not exist). We can factor in sub-exponential time, but the
> fastest algorithms for solving general NP-complete problems take
> exponential time.
>
> Scott
I think there is a proof that if factoring is NP-complete, then either
P=NP, or the extended Riemann hypothesis fails. I vaguely remember this
is referenced in Garey and Johnson (but i've lost my copy). A lot of
people would consider this to prove that factoring is not NP-complete,
although technically it is not quite such a proof.
It hinges on factoring being (almost certainly) in co-NP.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: 29 May 2000 04:19:21 GMT
In <[EMAIL PROTECTED]> root <[EMAIL PROTECTED]> writes:
If P=NP, then any problem which is polynomial chechable is polynomial
solvable. Since encryption is polynomial checkable ( assuming you can
extend the idea of "length" to length of key and extend any algorithm to
an arbitrary length key so tht the notion of polynomial growth can be
defined.) and if P=NP then any encryption scheme is solvable in
polynominal time.
At least I suspect that is the argument. Of course an encryption scheme
solvable in L^(10^5) is not much better than one in exponential time.
]In the paper last week there was an article about 7 math
]problems for the 21st century. One of them (P = NP) was
]supposed to allow easy breaking of encryption.
]I went to the site (www.claymath.org) and looked at the
]problem description. They suggested that if someone could
]solve a problem like Hamilton Circuit (path through nodes
]visiting each one only once, ending at starting point), then
]the safety of encryption is gone.
There exist a set of NP problems called NP complete which are such that
any NP problem can be solved in terms of an NP complete problem, so that
if one of them is solved in P, then all are. I suspect the Hamilton
Circuit is one such.
Again, P can be pretty intractable as well. In fact even low powers of
can grow so fast that they are essentially unsolvable.
]Is this hype? Would it still take a lot of work? How would
]someone use a solution for Hamilton Circuit to break RSA
]for instance?
Factoring is an NP problem. Ie it is checkable in polynomial time (
which is the definition of NP).
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Math problem (P=NP) prize and breaking encryption
Date: 29 May 2000 04:08:29 GMT
root <[EMAIL PROTECTED]> wrote:
> In the paper last week there was an article about 7 math
> problems for the 21st century. One of them (P = NP) was
> supposed to allow easy breaking of encryption.
It's more than that. A constructive proof that P = NP which
took the form of a very efficient (i.e. low polynomial time)
algorithm for solving any problem in NP would change the world.
Not just in cryptography, either.
Here's some terminology :
The class of problems NP is the class of all problems whose answer
can be "checked quickly." That is, if I give you the problem "factor N",
and two numbers p and q which I claim are the answer, you can easily check
that answer. You just multiply the numbers together. The class P is a
subset of this where _finding_ the answer is quick, not just checking it.
The standard of "quick" which we use is to consider an algorithm "quick"
if it takes a number of steps bounded by a polynomial in the size of the
input. The notion of a "number of steps" depends on your model of
computation, but it basically means what you probably think it means.
The reason I have so many qualifiers is
that we can imagine several other ways that it could be proved
"P = NP", but still there remain "hard" problems of the kind
needed for crypto and dreaded in other disciplines. For example,
someone might prove that all problems in NP can be solved in exactly
n^100 steps -- i.e. you can do better for easier problems, but it's
not possible to be harder, and for "generic" problems that's the best
you can do. For relatively small values of n, this is intractable.
But it's still a polynomial.
That would prove P = NP, but it would *also* possibly put crypto on firmer
foundations than we have today. At least, it would be some provable
hardness which we could try to exploit. Does anyone out there know the
best lower bound we can prove for anything?
There are also issues with average-case vs. worst-case hardness.
Impagliazzo's paper on "A Personal View of Average-Case COmplexity" is
a neat overview of the possible consquences of various answers to
the question "P ?=NP". You can find it at
http://www-cse.ucsd.edu/users/russell/average.ps
> I went to the site (www.claymath.org) and looked at the
> problem description. They suggested that if someone could
Coincidentally, I am indebted to these people. They are kindly
sponsoring a summer school on computational complexity theory in
coordination with the Park City Math Institute. I'm attending
the undergrad program thanks to CMI's generous support.
The page for that is at
http://www.admin.ias.edu/ma/SummerSession2000.htm
> I'm certainly not an expert in encryption, but I was curious
> how such an unrelated problem could have anything to do with
> breaking encryption.
There must exist a way of taking a number N to be factored, and then
creating graphs such that IF we knew the hamiltonian circuits of
these graphs, THEN we would know the factors of N. I don't know what it
is, but I know such a way must exist.
The reason is that hamiltonian circuit is an "NP-hard" problem. That means
that for every problem in NP, there is a way of reformulating the problem
in terms of a HC problem. Factoring is in NP, so it must have a way of
being expressed in terms of HC.
Why is HC NP-hard? Answering that involves defining a Turing Machine, and
then introducing the notion of "nondeterminism". Then we can define NP
differently -- as "the class of all languages accepted by a
nondeterministic turing machine which halts in polynomial time." Finally
we would show that answering that question and answering HC in general
is equivalent. I can try to do that if you like, but a better place to
look would be a textbook on the theory of computation.
Thanks,
-David
------------------------------
From: Postmaster@[127.0.0.1] (real address at end of post)
Subject: Re: encryption without zeros
Date: 29 May 2000 04:38:34 GMT
With any existing stream cipher (including any block cipher in OFB mode)
that uses a simple combiner (e.g. XOR or addition), change the combiner
to ones complement addition (decrypt with ones complement subtraction).
If plaintext is never zero, ciphertext will never be zero. Most CPUs use
twos complement math, but they also have "add with carry" and "subtract
with borrow" instructions. These instructions can be used for conversion
of twos complement math to ones complement. Following a twos complement
addition with an addition of zero using an "add with carry" instruction
converts the twos complement sum to a ones complement sum. The same
thing can be done with subtraction and "subtract with borrow". This is
fast and deterministic whereas the usual "re-encrypt until you don't get
a zero" is not. [patent pending]
--
Don'[EMAIL PROTECTED]
Kevin R. Driscoll, Staff Research Scientist PHONE: (612) 951-7263 FAX: -7438
POST: Honeywell M/S MN65-2200; 3660 Technology Drive; Mpls, MN 55418-1006; USA
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: No-Key Encryption
Date: Sun, 28 May 2000 22:14:52 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Steve Roberts) wrote:
>
> Er, ROT-13 *does* have a key - it's the "13" in the name. Maybe it
> could be called "Known-Key Encryption"
> Watch out for my new improved cipher ROT-X, which does not have this
> weakness.... .....
>
> Steve Roberts
If you consider a Caesar Cipher as having 25 keys, ROT13 is only one of
them. The bigest weakness here is in thinking that a single
monoalphabetic substitution system is apt to be anything but weak in any
form, but still fun for those that like it.
Remember that simple substitution is merely a primative in itself, called
that for good reason.
And, any base changing algorithm may be keyed or not. If in a native form,
the structure is the key. However, user assigned keys are easy to add to
such things. If one implementation does only simple ROT13, you might say
is unkeyed, but another implementation might allow you to use different
offsets as well.
The following is this sentence rotated 10 mod 26, instead of 13 mod 26.
Notice that I ignore the digits here:
Dro pyvvygsxq sc drsc coxdoxmo bydkdon 10 wyn 26, sxcdokn yp 13 wyn 26.
Xydsmo drkd S sqxybo dro nsqsdc robo:
--
If a privacy policy is longer that 250 words, it is already
deceptive; the longer the more deceptive.
------------------------------
** 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
******************************
