Cryptography-Digest Digest #2, Volume #12 Sun, 11 Jun 00 04:13:01 EDT
Contents:
Re: Call for evaluating and testing a stream cipher program
([EMAIL PROTECTED])
Re: Digits of pi in Twofish (Terry Ritter)
Re: Chronological Backtracking in Scheme (James Pate Williams, Jr.)
Re: Digits of pi in Twofish (Jim Gillogly)
Re: How does DES work? ("Douglas A. Gwyn")
Re: Cryptanalytic gap [was: Re: Some dumb questions] ("Douglas A. Gwyn")
Re: Question about recommended keysizes (768 bit RSA) (Jerry Coffin)
Re: Cipher design a fading field? ("Douglas A. Gwyn")
Re: Comments on "Encase" forum about EE ("Douglas A. Gwyn")
Re: encoding of passwords ("Wouter")
Re: encoding of passwords ("Wouter")
Re: randomness tests (Guy Macon)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Reply-To: [EMAIL PROTECTED]
Subject: Re: Call for evaluating and testing a stream cipher program
Date: Sat, 10 Jun 2000 22:28:05 -0700
I did not realize that your absurd and hostile comments were "specific
questions." If you had read my description they would not even occur to you. But
here are the answers:
1) I was not joking
2) I do know what BBS is.
3) I do not "post-process" it. There are several PRNGs running in parallel at
different speeds. The BBS generates one random number for each 262144 random
numbers generated by the fastest running LFG.
4) That is how I can mention "fast" and "BBS" in the same context.
I hope this answers your questions.
CascadeResearch
tomstd wrote:
> You are obviously some kinda of troll. You responded with the
> exact same message three times after I asked specific questions.
>
> Bye.
>
> 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] (Terry Ritter)
Subject: Re: Digits of pi in Twofish
Date: Sun, 11 Jun 2000 05:24:57 GMT
On Sun, 11 Jun 2000 04:51:16 +0000, in <[EMAIL PROTECTED]>, in
sci.crypt Jim Gillogly <[EMAIL PROTECTED]> wrote:
>tomstd wrote:
>>
>> it's blowfish not twofish that uses pi, and there is absolutely
>> no cryptographic reason to the best of my limited knowledge
>
>'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?
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (James Pate Williams, Jr.)
Subject: Re: Chronological Backtracking in Scheme
Date: Sun, 11 Jun 2000 06:01:32 GMT
The following post is somewhat off-topic for sci.crypt, but may be of
interest to a small minority of lurkers and regulars. Much better ways
exist for solving the n-queens problem, such as backmarking,
forward checking, min-conflicts hill-climbing, et cetera.
; solution of the n-queens problem using chronological backtracking
; _Foundations of Constraint Satisfaction_ by Edward Tsang page 37
(define constraints-violated-inner-loop-iter
(lambda (a i j n q)
(cond ((= j n) 0)
(else
(let ((b (list-ref q j)))
(cond ((and (not (= i j)) (not (= a -1)) (not (= b -1)))
(if (= a b)
(+ 1 (constraints-violated-inner-loop-iter
i (+ j 1) n q))
(let ((ij (- i j)))
(if (or (= ij (- a b)) (= ij (- b a)))
(+ 1
(constraints-violated-inner-loop-iter a i (+ j 1) n q))
(+ 0
(constraints-violated-inner-loop-iter a i (+ j 1) n q))))))
(else (+ 0 (constraints-violated-inner-loop-iter
a i (+ j 1) n q)))))))))
(define constraints-violated-inner-loop
(lambda (a i n q)
(constraints-violated-inner-loop-iter a i 0 n q)))
(define constraints-violated-outer-loop
(lambda (i n q)
(cond ((= i n)
0)
(else
(+ (constraints-violated-inner-loop (list-ref q i)
i n q)
(constraints-violated-outer-loop (+ i 1) n q))))))
(define constraints-violated
(lambda (n q)
(constraints-violated-outer-loop 0 n q)))
(define create-domain-iter
(lambda (i n)
(if (= i n)
()
(cons i (create-domain-iter (+ i 1) n)))))
(define create-domain
(lambda (n)
(create-domain-iter 0 n)))
(define delete-element-iter
(lambda (element i lst)
(if (= i (length lst))
()
(if (= element (list-ref lst i))
(delete-element-iter element (+ i 1) lst)
(cons (list-ref lst i) (delete-element-iter element (+ i
1) lst))))))
(define delete-element
(lambda (element lst)
(delete-element-iter element 0 lst)))
(define n-queens-back-track-loop-iter
(lambda (compound-label domain-x n unlabelled x)
(if (null? domain-x)
()
(let ((j (random (length domain-x))))
(let ((v (list-ref domain-x j)))
(if (= (constraints-violated n (cons v compound-label)) 0)
(cons v (n-queens-back-track-loop-iter (cons v
compound-label)
(delete-element
v domain-x)
n
(delete-element
x unlabelled)
x))
(n-queens-back-track-loop-iter compound-label
(delete-element v
domain-x)
n
unlabelled
x)))))))
(define n-queens-back-track-loop
(lambda (compound-label domain-x n unlabelled x)
(let ((cl (n-queens-back-track-loop-iter compound-label domain-x n
unlabelled x)))
(if (null? cl)
()
cl))))
(define n-queens-back-track
(lambda (compound-label n unlabelled)
(let ((domain-x (create-domain n))
(i (random (length unlabelled))))
(let ((x (list-ref unlabelled i)))
(let ((lst (n-queens-back-track-loop compound-label domain-x n
unlabelled x)))
(if (and (= (length lst) n) (not (= (list-ref lst (- (length
lst) 1)) -1)))
lst
(n-queens-back-track compound-label n unlabelled)))))))
(define init-compound-label
(lambda (i n)
(if (= i n)
()
(cons -1 (init-compound-label (+ i 1) n)))))
(define init-unlabelled
(lambda (i n)
(if (= i n)
()
(cons i (init-unlabelled (+ i 1) n)))))
(define display-n-queens-solution-line-iter
(lambda (counter n)
(cond ((= counter n)
(display "=")
(newline))
(else
(display "====")
(display-n-queens-solution-line-iter (+ counter 1) n)))))
(define display-n-queens-solution-line
(lambda (n)
(display-n-queens-solution-line-iter 0 n)))
(define display-n-queens-solution-col-iter
(lambda (col n q)
(cond ((= col n)
(display "|")
(newline))
(else
(display "| ")
(if (= col q)
(display "Q ")
(display " "))
(display-n-queens-solution-col-iter (+ col 1) n q)))))
(define display-n-queens-solution-col
(lambda (n q)
(display-n-queens-solution-line n)
(display-n-queens-solution-col-iter 0 n q)))
(define display-n-queens-solution-row-iter
(lambda (compound-label n row)
(cond ((= row n)
())
(else
(display-n-queens-solution-col n (car compound-label))
(display-n-queens-solution-row-iter (cdr compound-label) n
(+ row 1))))))
(define display-n-queens-solution-row
(lambda (compound-label n)
(display-n-queens-solution-row-iter compound-label n 0)))
(define display-n-queens-solution
(lambda (n)
(let ((compound-label (n-queens-back-track
(init-compound-label 0 n)
n
(init-unlabelled 0 n))))
(display-n-queens-solution-row compound-label n)
(display-n-queens-solution-line n))))
(display-n-queens-solution 5)
Using DrScheme we have:
Welcome to DrScheme, version 101.
Language: Graphical Full Scheme (MrEd).
=====================
| Q | | | | |
=====================
| | | Q | | |
=====================
| | | | | Q |
=====================
| | Q | | | |
=====================
| | | | Q | |
=====================
==Pate Williams==
[EMAIL PROTECTED]
http://www.mindspring.com/~pate
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Digits of pi in Twofish
Date: Sun, 11 Jun 2000 06:18:47 +0000
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. 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.
--
Jim Gillogly
Hevensday, 22 Forelithe S.R. 2000, 06:13
12.19.7.5.2, 2 Ik 5 Zotz, Third Lord of Night
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: How does DES work?
Date: Sun, 11 Jun 2000 06:25:15 GMT
tomstd wrote:
> DES is certainly a dead cipher, ...
DES is hardly "dead".
(a) DES is widely used in commerce.
(b) DES is a component of 3DES, which is widely used.
(c) The widely-known sub-brute-force attack (so-called "linear
cryptanalysis") does not amount to a practical attack under
normal circumstances.
(d) However, DSES is known to be susceptible to brute-force attack
if enough resources are used, so it is not recommended for the
highest level of security (not that it ever was).
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cryptanalytic gap [was: Re: Some dumb questions]
Date: Sun, 11 Jun 2000 06:34:24 GMT
John Savard wrote:
> ... Anything that isn't an OTP can, in theory, be solved: ...
No.
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Question about recommended keysizes (768 bit RSA)
Date: Sun, 11 Jun 2000 00:43:35 -0600
In article <8hu3oo$5tm$[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> The problem is, there were no $2,000 computers in 1977 and there were
> no desktop class machines so (in some sense) ANY comparison might
> be criticized by someone looking for an excuse to be critical.
No, the real problem is that absolutely EVERY statement in the
paragraph above is utterly, totally, 100% false from beginning to
end. There WERE $2000 desktop computers in 1977. I've already
pointed out that the Apple II and the Altair were two of them. In
case you want more, consider the SWTPC and the IMSAI.
EVERY ONE of these had a 1 MHz, 8-bit bus to memory, AND none of them
had a cache on the chip, so the bus had to be divided between data
and code usage. Worse yet, these chips were heavily microcoded, so
most of them could really only move one byte of data every third or
fourth clock cycle or so.
The Pentium has a 64-bit, 133 MHz bus to memory and has on-board
cache large enough to hold sieving code in its entirety, so that
nearly that entire bandwidth can be used for data operations. IOW,
bandwidth to memory in single-user, desktop machines has improved by
a factor of at least 2,000:1 instead of the roughly 10:1 that your
comparison claimed. Due to improvements elsewhere, the real
improvement is considerably greater still, somewhere around 5,000 or
6,000:1 instead.
In fairness, this IS still somewhat short of what we'd expect from
Moore's observation: realistically we're looking at an increase of
somewhere around 5,000:1 and even doubling every 2 years since 1977
would give an increase over triple that.
Ultimately, almost any comparison would leave SOME room for argument
and criticism: exact levels of optimization, ancillary components on
motherboards, the 2.5 MHz 8080A perhaps being avaialable though as
yet nearly unused in 1977, etc., will all affect real memory
bandwidth to at least some degree. Even at worst, however, all these
factors combined are unlikely to give an error of more than a single
order of magnitude, while your comparison was so flawed that it
started with an error of at least two orders of magnitude, and in
reality the error is probably closer to three orders of magnitude.
IMO, given the nature of the paper one can and should expect to see
some errors -- even if the comparisons were perfect, they still
couldn't and wouldn't give a perfect prediction of the future anyway.
Errors of more like three orders of magnitude are a considerably
different story: they're simply too large for anybody to reasonably
ignore.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Cipher design a fading field?
Date: Sun, 11 Jun 2000 07:15:05 GMT
John Savard wrote:
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
> >John Savard wrote:
> >> But some people have expressed a wish for proofs of security for
> >> ciphers, and in my opinion, that looks like something equivalent to
> >> solving the halting problem.
> >Maybe an attempt to prove that equivalence would prove enlightening.
> Well, to see if such an attempt is feasible, let us review ...
> This, however, assumes that the time a computer program that will
> eventually halt will take to run is unbounded, thus, the term
> "computer program" is meant in the abstract, and includes programs of
> unbounded size, requiring unbounded amounts of memory.
Actually the programs involved don't have to be very large.
Chaitin has a rather small one for his specialized version of LISP.
> Since this proof depends on our ability to determine the status of
> _any_ program, if we restrict ourselves to just one narrow kind of
> program, the proof may not apply. The question that would need to be
> decided here is: is trying to find a way to crack a cipher a very
> narrow subset of mathematics, or is it open-ended enough that one
> could, for just about any mathematical conjecture, design a cipher
> such that finding a solution to that cipher, or proving one did not
> exist, was equivalent to finding a counterexample, or proving, the
> conjecture? That is a difficult question: how would one design, for
> example, a cipher that was secure if and only if Goldbach's Conjecture
> is true? On the other hand, cipher design does seem to be fairly
> open-ended.
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.
Now, I'm sure that one can take an effectively computable valid
encryption function and tweak it so that it becomes ineffective,
but from the cryptanalyst's point of view it is the equivalent
effective encryption that matters.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Comments on "Encase" forum about EE
Date: Sun, 11 Jun 2000 07:17:40 GMT
[EMAIL PROTECTED] wrote:
> But here is an opportunity for EE support to do what their name
> implies - support their users in this forum.
Goddammit, if EE wants a support forum they can start one.
sci.crypt is *not* an appropriate place for customer support
nor for the flaming pro and con about commercial products.
------------------------------
From: "Wouter" <[EMAIL PROTECTED]>
Subject: Re: encoding of passwords
Date: Sun, 11 Jun 2000 09:36:41 +0200
>Each character in the file /etc/passd is encoded with 6 bits. That
>makes 64 characters, all printable.
>The algorithm is a variation on DES; in fact, there are 4096
>variations, and the variation used is indicated by the first 2
>characters of the encrypted password. These two characters are called
>"salt ".
>The password is used as the key to encrypt the value 00000000 (8 times
>zero). DES keys are 56 bits, each character is 7 bits.
>Contrary to DES, there is not 16 turns but 400 (in the lastest
>version). The result of these 400 turns is a word of 64 bits cut in 10
>pieces of 6 bits and 1 piece of 4 bits which is 11 characters. Plus
>the salt = 13 characters.
Thank you very much. This is exactly what I wanted to know. There's one
thing I don't know yet: the DES algorithm I know don't use a 'salt' (there
are not 4096 different variations). What part of the DES algorithm is
different and what is the new one (the part of the algorithm which uses this
salt)?
I hope somebody can answer this question too.
Wouter.
------------------------------
From: "Wouter" <[EMAIL PROTECTED]>
Subject: Re: encoding of passwords
Date: Sun, 11 Jun 2000 09:40:07 +0200
[EMAIL PROTECTED] wrote in message
<8hrnc3$jar$[EMAIL PROTECTED]>...
>In article <e7WhrFk0$GA.297@net025s>,
> "Wouter" <[EMAIL PROTECTED]> wrote:
>> I want to know how the encoding of password occurs in Unix / Linux
>> -systems (the /etc/passwd file).
>
>Wouter, it depends on the distribution. Some distributions (Debian at
>least, and FreeBSD as well afaik) don't use DES, but rather MD5. Others
>(OpenBSD) use Blowfish with a configurable number of applications.
Thanks for the reaction. It's good to know that not all distributions uses
the same algorithm. But I know that my system uses DES encryption and I want
to write a program which does the same (encrypting passwords).
Wouter.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: randomness tests
Date: 11 Jun 2000 04:07:37 EDT
tomstd wrote:
>
>Again, total garbage. The original poster never said what he is
>using the prng for so how can you be sure that these tests are
>good for what he needs?
>
>Would people stop clinging to Diehard/ent/etc as the ONLY way to
>test a prng!!!! IF you don't know what it's for, how can you
>tell if it's good or not?
>
There are people who make software PRNGs and other people who
make hardware RNGs which are for sale. Those people don't know
what it's for. What would you advise them to do about testing?
In particular, the people who make hardware RNGs are shooting for
true randomness, and may have acheved this goal. For them failing
ANY randomness test is unacceptable, so all such tests are useful.
------------------------------
** 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
******************************
