Cryptography-Digest Digest #13, Volume #12 Mon, 12 Jun 00 21:13:01 EDT
Contents:
Re: Random sboxes... real info (tomstd)
Re: Symbolic Differentiation in Scheme (James Pate Williams, Jr.)
And the search is on! (tomstd)
Re: More papers online ("Joseph Ashwood")
Re: And the search is on! (tomstd)
Re: More papers online (tomstd)
Re: How does DES work? ("Joseph Ashwood")
Re: And the search is on! ("Joseph Ashwood")
Is Gretchen down? (Anonymous)
Re: And the search is on! (tomstd)
Re: How does DES work? (tomstd)
Re: And the search is on! (tomstd)
Re: Updated: Evidence Eliminator Dis-Information Center (Includes info on false SPAM
accusations) ("donoli")
Re: Updated: Evidence Eliminator Dis-Information Center (Includes info on false SPAM
accusations) (tomstd)
Finding prime numbers (AllanW)
Re: Is Gretchen down? (Stray Cat)
Re: Digits of pi in Twofish (Jim Flanagan)
----------------------------------------------------------------------------
Subject: Re: Random sboxes... real info
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 16:08:52 -0700
In article <8i3o7m$q93$[EMAIL PROTECTED]>, Rex Stewart
<[EMAIL PROTECTED]> wrote:
>Writing software to output "good" or "great" S-boxes might be
>a good idea. But knowing Tom, he'd only keep the "great" ones
>around :-) His standards seem pretty steep.
Yea, only the best from tom.. hehehehe
>Now, for the real question. Am I still reading this wrong, or
>did your overnight test fail virtually all of the S-boxes on
>LP-max and ALL of them on DP-max? If that IS the case, maybe
>there SHOULD be some work on an algorythm to output S-boxes that
>always pass these tests. (But not until after final exams.)
>
Out of the 49,000 sboxes fully tested overnight none of them had
ideal properties. However my SBOXGEN program does early-out
testing so I can test 49,000 sboxes in about 8 seconds on my
comp. Basically as soon as I find the sbox sub-optimal I stop
testing it. Whereas in my overnight test I fully tested all
sboxes. All in all I had to test about 30 million sboxes to
come up with four good 8x8 sboxes. They have a LP of 1/8, a DP
of 1/32, fullfils SAC and BIC and has a non-linear order (using
LP=1/8) of 7. They are available on from my site as
http://tomstdenis.com/four_8x8.c
The best known 8x8 sboxes with regard to LP and DP are the
inversions in GF(2^8), however those sboxes fail to meet SAC and
have a low nonlinear order of 2.
And you can get my SBOXGEN program free of charge from
http://tomstdenis.com/
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: Symbolic Differentiation in Scheme
Date: Mon, 12 Jun 2000 23:50:20 GMT
Somewhat off-topic, but could be of some interest to readers of this
group.
; code from _Structure and Interpretation of
; Computer Programs_ by Harold Abelson et al.
; pages 147 - 150
(define (=number? n1 n2)
(and (number? n1) (number? n2) (= n1 n2)))
(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (list '+ a1 a2))))
(define (make-product m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (list '* m1 m2))))
(define (sum? x)
(and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))
(define (product? x)
(and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))
(define (deriv exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
((product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))
(else
(error "unknown expression type -- DERIV" exp))))
(deriv '(+ x 3) 'x)
(deriv '(* x y) 'x)
; new code by James Pate Williams, Jr. (c) 2000
; f(x) * f(x) * f(x) = (pow f(x) 3)
; exponent is assumed to be a number
(define (make-exponentiation t e)
(cond ((=number? e 0) 1)
((=number? e 1) t)
((=number? t 0) 0)
((=number? t 1) 1)
((and (number? t) (number? e))
(exp (* e (log t))))
(else (list 'pow t e))))
(define (base p) (cadr p))
(define (exponent p) (caddr p))
(define (exponentiation? x)
(and (pair? x) (eq? (car x) 'pow) (number? (exponent x))))
(define (deriv exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
((product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))
((exponentiation? exp)
(make-product
(make-product (exponent exp)
(make-exponentiation (base exp)
(- (exponent exp) 1)))
(deriv (base exp) var)))
(else
(error "unknown expression type -- DERIV" exp))))
(deriv '(pow (* x y) 4) 'x)
==Pate Williams==
[EMAIL PROTECTED]
http://mindspring.com/~pate
------------------------------
Subject: And the search is on!
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 16:41:59 -0700
Using my Sboxgen [1] program I am foolishly [2] searching
for 'perfect' 8x8 sboxes. If you want to help in this silly [2]
search then pick up a copy of sboxgen and use the following
settings
input/output size: 8 8
Max linear trait: -16 16
Max diff trait: 2
inverse: 0
sac: 1
sc: 0
bic: 1
order: 7
bic nonlinear: 16
If you need help setting it up just ask. I would be surprised
to ever see one made by my program, but it's worth a shot. I
have three computers running it already... Let's see what
happens.
[1] sboxgen: http://tomstdenis.com/sboxgen.c
[2] Foolish: Definition. Trying to find perfect sboxes by
randomly making them.
* 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: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: More papers online
Date: Mon, 12 Jun 2000 16:46:45 -0700
Well, when you find it, make sure you tell me at least.
Joe
"tomstd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <eZ$Qk7L1$GA.328@cpmsnbbsa07>, "Joseph Ashwood"
> <[EMAIL PROTECTED]> wrote:
> >> If anyone has a good easy to access collection of papers
> please
> >> post the links :-)
> >I've found Counterpane's to be very good:
> >http://www.counterpane.com/biblio/
> > Joe
>
> It is, but that's not the site I was thinking of.
>
> Thanks for posting the link.
>
> 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: Re: And the search is on!
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 16:49:21 -0700
Just out of curiosity, if I wrote a small Windows program that
runs this search at IDLE priority how many people would help me
run it?
I could have the program ready for this week...
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: Re: More papers online
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 16:52:25 -0700
In article <emX29iM1$GA.323@cpmsnbbsa07>, "Joseph Ashwood"
<[EMAIL PROTECTED]> wrote:
>Well, when you find it, make sure you tell me at least.
> Joe
Sounds like a plan.
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: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: How does DES work?
Date: Mon, 12 Jun 2000 17:02:34 -0700
I do not consider 2^243 to be broken, because the basis is 2^256, so only
about 5% of the bits would be gone. In DES the same 13 bits was 23%. If 23%
of the bits were cryptanalyzed away from an AES finalist I would consider it
broken, at least for the requirements of becoming AES, even though that
would leave over 200 bits of potential security. The same as if some person
were to develop 2000 bit encryption I would consider it broken if it were to
drop to 1500 bits, even though that is so far beyond possibility as to be
considered impossible. All of the attacks that do not successfully break a
cipher, I take as a guideline of the expectable strength of the cipher, and
I consider it along a roughly exponential function. If .00000001 % of the
key space has been cryptanalyzed away, the next breakthrough will probably
eliminate another .00000001 % of the space, followed by one that eliminates
roughly twice that, and so forth, very slow growth indeed. Once 15+% of the
key space has been eliminated, it becomes very obvious that the cipher is
aging, and is likely to be broken at any moment. Of course such methods do
not always accurately predict progress, but looking at history it seems to
be followed often enough to be a useful estimate (at least to me).
I looked a second time at what you wrote, I'm still can't see where I was
being hypocritical, I was simply contending that if we were to eliminate all
ciphers once the first flaw was found, we wouldn't have any ciphers left
(barring OTP, which is unrealizable), and that I actually found the
published attacks against the AES finalists comforting because they exposed
no significant weaknesses.
Joe
"tomstd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <eZcxp7J1$GA.325@cpmsnbbsa07>, "Joseph Ashwood"
> <[EMAIL PROTECTED]> wrote:
> >> Even the slightest weakness
> >> should be reason enough to stop using a cipher.
> >But we have no perfect ciphers. Every AES finalist has been
> shown to have
> >extremely minor weaknesses against something, and to be based
> on assumptions
> >that we cannot prove. I think we can agree that those 5 are the
> best of the
> >best right now. I find it encouraging that the attacks are so
> close to the
> >difficulty of a brute force search.
>
> Now don't be hypocritical my friend. The best attack on DES is
> about as close to the bruteforce as well (well off by 2^13).
>
> I don't want to put words in your mouth, but by your previously
> expressed logic if a AES cipher can be broken by say 2^243 work
> then it would be weak as well?
>
> To be fair, i find it comforting that none of the AES finalists
> have been broken by conventional means of attack too.
>
> 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: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: And the search is on!
Date: Mon, 12 Jun 2000 17:04:04 -0700
I'd run it, at least when my systems weren't doing other things.
Joe
"tomstd" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Just out of curiosity, if I wrote a small Windows program that
> runs this search at IDLE priority how many people would help me
> run it?
>
> I could have the program ready for this week...
>
> 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!
>
------------------------------
Date: 13 Jun 2000 00:09:42 -0000
From: Anonymous <Use-Author-Supplied-Address-Header@[127.1]>
Subject: Is Gretchen down?
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
is it?
------------------------------
Subject: Re: And the search is on!
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 17:13:25 -0700
In article <OF4pJtM1$GA.330@cpmsnbbsa07>, "Joseph Ashwood"
<[EMAIL PROTECTED]> wrote:
>I'd run it, at least when my systems weren't doing other things.
> Joe
Cool, I will have to start it then. The program would take
about half a meg of ram at the most (most likely less) and be at
IDLE priority. It would be a taskbar (not tray) task that just
sits and runs.
To keep it simple when (or if) it finds an sbox I will just
write a .TXT file to the desktop and you can email it to me.
This will keep the size of the program down a bit (and
development time as well).
Let's do a bit of math. There are about 2^1684 possible 8-bit
permutations. Let's assume there are a trillion perfect 8x8
sboxes, our chances of finding an sbox is about 2^-1644, let's
assume there are only a million then we have 2^-1664. Finally I
am guessing there are only a handful of perfect sboxes (say a
thousand) we have a one in 2^1674 chance of finding one. These
odds are stacked against us, but I bet given enough time and
computers one of the sboxes will happen to fall out of the
clouds.
This says nothing about other construction techniques. I have
tried rudimentary CAST designs before and never had a great
success rate...
I should have it done for this weekend (I have exams this
week... arrg!!!)
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: Re: How does DES work?
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 17:16:50 -0700
In article <#azd0qM1$GA.329@cpmsnbbsa07>, "Joseph Ashwood"
<[EMAIL PROTECTED]> wrote:
>I do not consider 2^243 to be broken, because the basis is
2^256, so only
>about 5% of the bits would be gone. In DES the same 13 bits was
23%. If 23%
>of the bits were cryptanalyzed away from an AES finalist I
would consider it
>broken, at least for the requirements of becoming AES, even
though that
>would leave over 200 bits of potential security. The same as if
some person
>were to develop 2000 bit encryption I would consider it broken
if it were to
>drop to 1500 bits, even though that is so far beyond
possibility as to be
>considered impossible. All of the attacks that do not
successfully break a
>cipher, I take as a guideline of the expectable strength of the
cipher, and
>I consider it along a roughly exponential function.
If .00000001 % of the
>key space has been cryptanalyzed away, the next breakthrough
will probably
>eliminate another .00000001 % of the space, followed by one
that eliminates
>roughly twice that, and so forth, very slow growth indeed. Once
15+% of the
>key space has been eliminated, it becomes very obvious that the
cipher is
>aging, and is likely to be broken at any moment. Of course such
methods do
>not always accurately predict progress, but looking at history
it seems to
>be followed often enough to be a useful estimate (at least to
me).
>
>I looked a second time at what you wrote, I'm still can't see
where I was
>being hypocritical, I was simply contending that if we were to
eliminate all
>ciphers once the first flaw was found, we wouldn't have any
ciphers left
>(barring OTP, which is unrealizable), and that I actually found
the
>published attacks against the AES finalists comforting because
they exposed
>no significant weaknesses.
> Joe
I will agree with this. However, if you consider RC5 with a 128
bit key, by your logic 75 of the 128 bits have been removed due
to the differential attack (which has a workload of about
2^53). This is a loss of %58.6 which means RC5 is totally
broken and no longer secure.
That I don't agree with.
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: Re: And the search is on!
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 17:20:50 -0700
Even more math. My computer can test about 2^13.5 sboxes per
second or about 2^38.3 sboxes per *year*. This is hardly a
super speed. Assuming I tried this alone it would take me about
2^1625 years to find one (on average).
Even if I could bring my speed upto 2^20 per second it would
take 2^1618 years to find an sbox (average).
Hmm... lots of time ...
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: "donoli" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Subject: Re: Updated: Evidence Eliminator Dis-Information Center (Includes info on
false SPAM accusations)
Date: Tue, 13 Jun 2000 00:28:48 GMT
>What else explains the absolutely rabid hatred displayed towards EE by
>these miscreants who slander and malign to an extent that I have never
>seen done against any piece of software before?
>
>To find out the merits of EE is very simple: download the trial
>version and see for yourself. Simple, eh?
>
############
Why should one take a chance. I'm not for or against EE, but at this point
I just wouldn't take a chance on wiping out my HD, even if it only happened
the 2 times mentioned early in the thread.
Simple, eh?
donoli.
############
------------------------------
Subject: Re: Updated: Evidence Eliminator Dis-Information Center (Includes info on
false SPAM accusations)
From: tomstd <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Date: Mon, 12 Jun 2000 17:34:29 -0700
In article <[EMAIL PROTECTED]>, EE Support
<[EMAIL PROTECTED]> wrote:
>Hi all,
>
>Our news input feed at evidence-eliminator.com has been out for
a week
>due to a dud satellite. We haven't been able to correct this
weeks
>dis-information posts against our software directly, but:
>
>We have seen some posts coming on deja and remarq including
false
>"spam" accusations, etc, etc.
>
>We don't "SPAM" but we strongly believe in our right to dispute
and
>counter the hundreds of "SPAMMING" false messages posted to
security
>newsgroups about our software. It has become commonly said by
posters
>to these newsgroups that the ones posting the "anti-Evidence
>Eliminator" messages in all their disguises, are wearing badges
and
>intend to compromise your privacy and security, by stopping you
>downloading a free Evidence Eliminator.
>
>This week's false messages appear to span several newsgroups
listed in
>the header of this msg and this post is to counter those false
rumors.
>
>Our updated Dis-Information centre URL is:
>
>http://www.evidence-eliminator.com/dis-information.shtml
>
>Hope this helps,
Yadayayayayaya
Does tom care? Nope sorry.
If you want to confront SPAM don't SPAM the newsgroup. Just
contact the people DIRECTLY and tell them to shut their yappers.
By playing the victim you are trying to draw attention to your
super-duper wondersoftware. Which as I may remind the group is
NOT FREE and is CLOSED SOURCE.
My advice (this comming from a kid, so you can just close your
mind right now) is to IGNORE the other peoples derogatory
remarks and DISCUSS the merits of your software OBJECTIVELY by
making your source OPEN SOURCE. This doesn't mean it has to be
FREE by all means you want to make a living (I presume).
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: AllanW <[EMAIL PROTECTED]>
Subject: Finding prime numbers
Date: Tue, 13 Jun 2000 00:25:24 GMT
Suppose I had an algorithm so that, given a prime number P(n),
I could find the next prime number P(n+1) extremely quickly.
Let's say it was as quick as four or five integer additions.
(I don't actually have such an algorithm, but let's say I did.)
I'm guessing that an algorithm like this would make brute-force
attacks on private keys easier. Given a public key it would be
possible to derive the private key in a practical amount of
time, unless people started using much bigger keys than they
normally do now. And of course once the attacker had the
private key they could use it any way they wished.
Is that right?
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Stray Cat <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Subject: Re: Is Gretchen down?
Date: Tue, 13 Jun 2000 00:41:55 +0000
On 13 Jun 2000 00:09:42 -0000, Anonymous
<Use-Author-Supplied-Address-Header@[127.1]> wrote:
>is it?
>
>
No, but it is slow today.
--
You can contact me by posting to alt.anonymous.messages, ATTN: Stray Cat
New PGP Key. All others are obsolete.
PGP Key: 0x0CC6E051 finger: [EMAIL PROTECTED] for a copy.
Nym address is disabled. Don't send mail there.
DSS/Diffie-Hellman PGP Keys Will NOT Be Accepted.
------------------------------
From: Jim Flanagan <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To:
Subject: Re: Digits of pi in Twofish
Date: Mon, 12 Jun 2000 17:57:50 -0700
Terry Ritter wrote:
>
> Personally, I would say that e would be "the *most* obvious constant."
Actually, the Golden Mean is the most obvious constant. The continued fraction
expansion is [1,1,1,1,....].
--
Jim Flanagan
[EMAIL PROTECTED]
------------------------------
** 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
******************************
