Cryptography-Digest Digest #74, Volume #9 Fri, 12 Feb 99 13:13:04 EST
Contents:
Re: shuffling hexits (Walter Eric Johnson)
Re: RNG Product Feature Poll (Paul Crowley)
Re: On a Method of Session Key Generation (revised) (R. Knauer)
Re: RNG Product Feature Poll (R. Knauer)
Re: Factoring Complex Numbers ("Wm. Toldt")
Re: On a Method of Session Key Generation (revised) (R. Knauer)
Re: HELP!: seeking algorithms for coding theory problem (Sean Coffey)
Re: Factoring Complex Numbers (Safuat Hamdy)
Re: RNG Product Feature Poll (R. Knauer)
SSL Doc ("John")
New high-security 56-bit DES: Less-DES ([EMAIL PROTECTED])
Re: shuffling hexits (wtshaw)
Re: RNG Product Feature Poll ("Tony T. Warnock")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Walter Eric Johnson)
Subject: Re: shuffling hexits
Date: 12 Feb 1999 11:39:28 GMT
wtshaw ([EMAIL PROTECTED]) wrote:
: ... (Canadian is a river and also a city in Texas at about
: 100W 36N.) ...
Don't forget the dinosaur overlooking the highway a few miles
south of Canadian.
Eric Johnson
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: RNG Product Feature Poll
Date: 12 Feb 1999 09:46:36 -0000
[EMAIL PROTECTED] (R. Knauer) writes:
> >>"Equidistributed" does not
> >> necessarily mean independent. "Independent" does not necessarily mean
> >> equidistributed.
>
> >unbiased?
> A counter is almost perfectly unbiased (in the Champernowne sense),
> but certainly not equiprobable.
I've heard pretty much every failing a PRNG can suffer from described
as "bias", so usage may differ.
--
__
\/ o\ [EMAIL PROTECTED] http://www.hedonism.demon.co.uk/paul/ \ /
/\__/ Paul Crowley Upgrade your legacy NT machines to Linux /~\
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On a Method of Session Key Generation (revised)
Date: Fri, 12 Feb 1999 12:41:04 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 11 Feb 1999 22:42:36 -0600, [EMAIL PROTECTED] (wtshaw) wrote:
>OK, confidence is a statistical measure of how sure you are. In some
>areas of science, 0.05 level might be OK, which means you are 95% sure
>your results are OK. It has lots to do with sampling techniques. When
>you say crypto-grade, it should be defined in similiar form, like 0.001.
>An error range should also be specified.
I suppose it all depends on how much information you are willing to be
leaked. That in turn depends on how may cipher bits you plan to
generate.
I have asked the experts here to comment on how one might use a
Bayesian attack to quantify the level of security of a given TRNG, but
so far we have not gotten a response.
>Or, did you mean you needed explanation on the second part? I allude to
>an OTP and a pRNG in the same way, our wanting to make the series produced
>as little likely to be reproduced by some means as possible. If a pRNG is
>sufficiently obscure, then an OTP is not necessary. Consider that a pRNG
>can be very complex, its initial state including many variables.
If by PRNG, you mean any procedure to generate numbers, including
construction schemes, then I agree with you. I believe that one should
in principle be able to determine the level of security
experimentally, as suggested above. Whether that can be done
effectively is another question.
But I do not believe that passing statistical tests on the raw output
of a number generator provides any measure of security. It takes an
inference method to get at that, and statistical tests on the raw
output.
The Bayesian method alluded to above is an inferential attack on a
completed cipher, which contains intelligible information. That is,
the attack is based on uncovering something measurable, namely
intelligible messages. That makes it fundamentally distinct from
trying to use statistical tests to characterize a RNG from its
presumed random output.
>Be careful, most people have done criminal things, knowingly, or not.
Yeah, that's because when the politicians can't control honest people,
the govt makes laws to turn them into criminals, and they can be
controlled. We see that very thing happening in the crypto community.
>A criminal is only one who has been formally found guilty of a certain type
>of offense.
Yeah, found guilty by the very Establishment that makes those laws.
Interestingly, the Establishment never finds itself guilty of breaking
its own laws - like at the Waco Massacre.
We the people can find crooked politicians guilty without using their
crooked courts to do it. And we can punish them by not paying any
attention to them, and by voting in fresh crooks next election.
Hey, that's Demonocracy in action!
>Being dishonest is not necessarily criminal behavior, not suggested, as it
>could be.
It is when it breaks the public trust.
Bob Knauer
"The one thing every man fears is the unknown. When presented with this
scenario, individual rights will be willingly relinquished for the
guarantee of their well being granted to them by their world government."
--Henry Kissinger
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: RNG Product Feature Poll
Date: Fri, 12 Feb 1999 13:15:14 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 12 Feb 1999 05:56:40 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
>A random uniform generator is what you are looking for.
That's a bit circular, isn't it?
And the digits in Champernowne's number are almost uniform with regard
to bit groups, yet it is hardly a candidate for a TRNG.
I like the term "equiprobable" because it imparts the concepts of
independence and equidistributed in one word. I believe independence
and equidistributed are sufficient for a crypto-grade TRNG.
Independence means there are no correlations and equidistributed means
there is no bias. Numbers that have no bias or correlation cannot be
predicted, which means they are proveably secure for use in crypto.
Bob Knauer
"The one thing every man fears is the unknown. When presented with this
scenario, individual rights will be willingly relinquished for the
guarantee of their well being granted to them by their world government."
--Henry Kissinger
------------------------------
From: "Wm. Toldt" <[EMAIL PROTECTED]>
Subject: Re: Factoring Complex Numbers
Date: Fri, 12 Feb 1999 05:41:42 -1000
Lassi Hippeläinen wrote:
>
> Hey, why stop at complex numbers, why not use Hamilton's quaternions?
> And aren't there octaves, too?
>
> Complexity increases as dimension grows, but that is just security by
> obscurity. The pitfalls (bad keys etc.) probably increase even faster.
> There must be a group theorist somewhere out there who has an answer...
>
> -- Lassi
>
> > Trevor Jackson, III wrote:
> >
> > > How do you feel about factoring complex numbers whose terms are
> > > integral?
Sir William Rowan Hamilton in 1843 found the quaterions with four
elements. Ordinary rules of algebra hold, but multiplication is not
commutative. Maxwell mentioned them but was careful not to use them. Ben
Peirce invented linear associative algebras in 1870 but practical
applications were not found in physics and it became unpopular to
investigate higher numbers of elements beyond 4.
Wm. Toldt
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On a Method of Session Key Generation (revised)
Date: Fri, 12 Feb 1999 13:07:41 GMT
Reply-To: [EMAIL PROTECTED]
On 11 Feb 1999 22:32:36 GMT, [EMAIL PROTECTED] (Hal Finney)
wrote:
>Of course, "provably secure" is relative to a specific set of axioms.
I do not believe you can formally prove the security of any RNG (TRNG
or PRNG) by testing its output alone. In fact, Chaitin (whom you
mention below) believes that one cannot algortimically determine the
randomness of a number, even in terms of his algorithmic complexity
theory where some numbers are random and some are not random. In
crypto, all numbers are random - if they are produced by a TRNG.
I believe you can experimentally prove the security of a RNG to a
specified level of security by using the numbers to produce actual
ciphers which you then subject to an inferential attack like the
Bayesian method. If the ciphersleak no information, or only a
negligible amount of information in terms of your planned use of the
ciphers, then they are proveably secure for practical purposes.
That is a fundamentally different procedure from merely subjecting the
numbers themselves to statisitical tests.
>It is common, these days, for cryptographic proofs to in effect assume
>a stronger set of axiomatic assumptions, else, as you say, there would
>not be much work which could be done. The net result is that most work
>in cryptographic security is in the form of reductions, with one
>protocol's security being shown to have a specified relationship
>(implied by, equivalent to, implies, independent of...) to some other
>problem. BB&S is provably secure if we assume the hardness of
>quadratic reciduosity, etc.
The problem I have with such formal proofs is that they are no better
than the original conjecture (axiom) they are based on. The crypto
highway is littered with the corpses of "axiomatically proveably
secure" cryptosystems.
But the main problem I have is that crypto-grade randomness cannot be
characterized formally - there is no formal way to prove that the
numbers themslelves produced by a RNG are equiprobable - that is,
independently equidistributed.
Most cryptosystems do not depend on true randomness for security -
they depend on confusion. DES is not a random cryptosystem like the
OTP, it is a system that relies on massive confusion to produce
ciphers that are secure. And since it can be broken by brute force, it
does not depend on the randomness of its keys. By contrast, the OTP
cannot be broken by brute force, so it depends completely on its
random keys.
Crypto- grade confusion is not the same as crypto-grade randomness,
although people tend to blur the distinction between the two.
>The work of Greg Chaitin suggests viewing mathematics as a more
>exploratory discipline.
I am quite in agreement with Chaitin's position on "experimental
mathematics". The scheme alluded to above comes from considering his
position, in conjunction with Li and Vitanyi's comments on Bayesian
inference in their book on Kolmogorov Complexity, not applied to
random numbers themselves, but applied to the resulting ciphers
themselves.
>Rather than taking our axioms as given, we
>explore what fundamental assumptions are necessary to produce various
>proofs. Over time those assumptions may then become generally
>accepted. It may well be that eventually axioms will become well
>accepted which allow proving that P <> NP and that various mathematical
>cryptographic systems are secure.
But until then, basing crypto security on such assumptions is a crap
shoot. And who knows what will happen when Quantum Computers come on
line.
Bob Knauer
"The one thing every man fears is the unknown. When presented with this
scenario, individual rights will be willingly relinquished for the
guarantee of their well being granted to them by their world government."
--Henry Kissinger
------------------------------
From: [EMAIL PROTECTED] (Sean Coffey)
Crossposted-To: sci.math,sci.math.research
Subject: Re: HELP!: seeking algorithms for coding theory problem
Date: 12 Feb 1999 01:51:08 GMT
In article <[EMAIL PROTECTED]>,
Markus Grassl <[EMAIL PROTECTED]> wrote:
< list of papers on the decoding problem deleted >
There is an extensive review chapter by Alexander Barg in the newly
published "Handbook of Coding Theory" (eds. Pless and Huffman),
North-Holland '98. This covers the history of the algorithms that
have been put forward for all the (many) different versions of this
problem.
Sean Coffey
------------------------------
From: Safuat Hamdy <[EMAIL PROTECTED]>
Subject: Re: Factoring Complex Numbers
Date: 12 Feb 1999 15:19:32 +0100
"Wm. Toldt" <[EMAIL PROTECTED]> writes:
> I do not feel good about this problem. How would I
> factor 2380i-1884 or even know is a unique
> factorization exists?
Unique factorisation exists whenever the ring of numbers under consideration
is a principial ideal domain (PID).
> Maybe there are
> several complex factors which give
> the same result. Clearly another
> factorization exists:
>
> 2380i-1884 = 2(1190i-942)
This is as if you say 24 has factorisation 8 x 3 but 2 (4 x 3) is another
one. Clearly there are "primes" in rings like Z or Z[i], and primes in Z
aren't neccessarily prime in Z[i] i.e. any prime equivalent to 1 mod 4 is
uniquely expressible as a^2 + b^2 which is (a + b i)(a - b i), for instance
13 = 9 + 4 = (3 + 2 i)(3 - 2 i) = (2 + 3 i)(2 - 3 i) etc. Similar results
hold for other imaginary quadratic PIDs.
In fact, the ring of algebraic integers of Q[D] (D < 0 and = 0,1 mod 4 and
-D not a square in Z) is a PID exactly if and only if D = 3, 4, 7, 8, 11,
19, 43, 67, or 163 (by Heegner-Baker-Stark-theorem), an this are exactly
those algebraic integer rings, whose class group is trivial (i.e. has only
one element).
For other imaginary quadratic rings unique factorisation does not hold, but
it can be saved if you switch to ideals (and that's exactly why they were
"invented" by Kummer.)
> it is easy to calculate a composite number from several factors,
> but it is not possible to be sure which factors were used to
> generate the composite complex number. How can we use this
> one way hash capability to our advantage? It is unlike an
> RSA composite n=pq where n has unique factors.
Obsoleted by my above comment. Simply switch to ideals, and unique
factorisation in the maximal order holds. So you have to use nonmaximal
orders, where unique factorisation again does not hold generally, but in a
slightly smaller subset. All in all, your suggestion is not very promising.
--
S. Hamdy | All primes are odd except 2,
[EMAIL PROTECTED] | which is the oddest of all.
|
unsolicited commercial e-mail | D.E. Knuth
is strictly not welcome |
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: RNG Product Feature Poll
Date: Fri, 12 Feb 1999 13:31:17 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 12 Feb 1999 06:23:47 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>A white, uniform
>generator might work, but that phrase will trigger a lot of questions of the
>form "please define white" and "please definer uniform".
I believe the term "uniform distribution" is well defined in
statistics. However, as Li and Vitanyi point out in their book on
Kolmogorov Complexity, it is not sufficient to characterize
randomness.
>The terms independent
>and equidistributed will not trigger that kind of question.
I believe that to be a correct statement for reasons given earlier,
namely that "independent" implies lack of correlation and
"equidistributed" implies lack of bias. Numbers that lack correlation
and bias cannot be predicted.
Bob Knauer
"The one thing every man fears is the unknown. When presented with this
scenario, individual rights will be willingly relinquished for the
guarantee of their well being granted to them by their world government."
--Henry Kissinger
------------------------------
From: "John" <[EMAIL PROTECTED]>
Subject: SSL Doc
Date: Fri, 12 Feb 1999 17:18:14 +0100
Hi Guys,
I doubt this message has already been posted. Sorry for the inconvenience.
Could
any body point me to a good SSL documentation ?
Thanks in advance,
Regards,
John
------------------------------
From: [EMAIL PROTECTED]
Subject: New high-security 56-bit DES: Less-DES
Date: Fri, 12 Feb 1999 14:27:47 GMT
List:
I present below, for comments, the Less-DES protocol which offers
higher-security than DES and yet uses only the usual 56-bit DES key.
Hence, it is probably export-free and WA-free even though it could
take 2^14 times longer than DES, or more, to crack -- as discussed.
1. The protocol begins by Bob and Alice sharing a secret-key of
56-bits -- their symmetric-key for DES. This is the only key they
share or know of.
2. To send a message to Alice, Bob forms the first part of his
desired message as a plaintext block of 64 bits:
M1 = 0123...63
and uses DES with his 56-bit key in order to encrypt this 64-bit
block, forming the ciphertext also in a 64-bits block, as usual:
C1 = 0123...63
and then Bob simply cuts-off the last (for example) M-bits of that
64-bit block before actually sending the message to Alice:
C1' = 0123...(63-M)
For instance, if M=14, then Bob sends 64-bits *less* the 14-bits
(hence, the name Less-DES): C1' = 0123...49
3. The remaining M-bits, which were cut-off from that first block are
appended as the last M-bits of the next block's (63-M)-bits
plaintext, again forming a 64-bit plaintext:
M2 = 0123...(63-M) || (last M-bits of C1)
which is enciphered into C2:
C2 = 0123...63
which is also cut-off at the last M-bits before sending to Alice:
C2'= 0123...(63-M)
4. And so on, for all blocks of the message to the end.
5. To decode a message, Alice needs to discover the last M-bits for
the last ciphertext block -- in the example, since M-bits are cut-off
from the end of each block. The other M-bits for the other blocks
follow directly from the recovered plaintext of block K, to allow
decryption of block K-1. However, Alice can start decryption at *any*
block and work upwards -- so, a DoS attack by cutting off the last
block(s) is not possible.
Comment:
Since the last M-bits are missing for all blocks, their discovery is
essential to unambiguously define the plaintext. The attacker faces
a decryption workload of (56+M)-bits while Alice faces a workload
that is 2^56 times smaller. The recently discussed methods of
"plaintext hardening" (see Tony Bartoletti's postings) can be used
to advantage, to make the plaintext bits 0123...(63-M) have entropy
similar to the appended M-bits which were cut-off from a
random-looking ciphertext -- thus making a brute-force attack very
difficult {Ger99], though it must not be too difficult for Alice on
just M-bits versus the attacker on (56+M)-bits.
For M=14, Alice should take approximately one minute to solve the
14-bit problem, while EFF's DES Cracker (a powerful DES cracker in
hardware) would take approximately 75 years to solve the 70-bit
problem. To compare, the EFF DES Cracker would take approximately 40
hours for the usual 56-bit DES key.
Thus, Less-DES can significantly protect Bob & Alice's privacy,
without defining any other amount of shared-secret or even keying
material for anyone, beyond the initial 56-bit key. However, for
M=14, Less-DES has a brute-force attack time comparable to a 56 + 14
= 70-bit cipher.
This work is based on {Ger99] Section 5.2 and represents a different
implementation of the M-DES protocol -- where the unknown-key is
never explicit. In fact, the Less-DES protocol is the M-DES protocol
unfolded in two blocks -- where the last block provides a hint for
the one before.
The Less-DES protocol may answer concerns regarding possibly
diverging interpretations of export-free or WA terms -- since there
is no additional key in Less-DES, of any kind, not even ignored, when
security is enhanced from the 56-bit level. Thus, Less-DES offers a
direct security enhancement without any key addition over 56-bits.
This is of course also possibly useful for smart-cards, etc., where
lower processing power must be taking into account when designing a
protocol.
Other Less-DES modes are possible, such as providing no hints in
plaintext -- simply by letting Alice solve an open M-bit attack
problem on every block. Then, M can be considerably smaller -- for
example, 8 bits or less. All, as a function of needed security and
cost.
Comments are welcome.
Cheers,
Ed Gerck
=======================
REFERENCES:
[Ger99] Gerck, E., "Unicity, DES Unicity, Open-Keys; Unknown-Keys",
in http://www.mcg.org.br/unicity.htm
______________________________________________________________________
Dr.rer.nat. E. Gerck [EMAIL PROTECTED]
http://novaware.com.br
--- Meta-Certificate Group member -- http://www.mcg.org.br ---
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: shuffling hexits
Date: Fri, 12 Feb 1999 10:25:12 -0600
In article <7a13tg$fsq$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Walter
Eric Johnson) wrote:
> wtshaw ([EMAIL PROTECTED]) wrote:
> : ... (Canadian is a river and also a city in Texas at about
> : 100W 36N.) ...
>
> Don't forget the dinosaur overlooking the highway a few miles
> south of Canadian.
>
> Eric Johnson
Come over to Glen Rose and see the footprints, real ones.
As far at these various simple block ciphers being in the dinosaur realm,
don't know, but likely some are not as viable as others.
When you see some of these simple implementations down the way that use
shuffling of several different kinds of information units in the same
algorithm with no commonality between the units that could in brute
forcing, they might be more impressive, very long keys that nip simple
searches.
I try to stay away from rounds as such. That snake can bit me since I
have not dwelt on it sufficiently, but I will revisit them at some time.
Meanwhile, the translational ciphers are really attractive to do. This
particular kind of ciphers tend to have problems with rounds, but that is
not necessarily bad as many dissimiliar layers of substitution and
transposition can be stacked nicely together instead. A by product is a
large key space for what can be small groups.
There is always a change from plaintext to ciphertext, but it can be
increase or decrease in length in characters, with different bases much
the reason for that. The formulas are quite varied, many fitting nicely
together, some not. Some of the awkward ones can work with the bucket
technique. Others combinations are simply not attractive.
I try to adhere to some basic mathematical criteria to guide me:
conversion constants +- 10%, and less than about 10^10. Ciphertexts
should reflect bases of 13 or more, oly a few exceptions above 100. For
ciphertext sets less than 26, use nulls from unused characters, or when a
set is nearby and inferior to a likely common one, fill in with the
necessary nulls to mask essential ciphertext.
Groups should generally be short enough to have the length of the final on
verified by inspection. Very long exceptions to the above should be usable
if a unispaced font is used and the last group is compared to prior ones
displayed above it. But, the group should still be displayed in one
line. I tend to do ones from the easy pile first, which include maybe a
couple of hundred of nice choices.
--
A much too common philosophy:
It's no fun to have power....unless you can abuse it.
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: RNG Product Feature Poll
Date: Fri, 12 Feb 1999 10:39:53 -0700
Reply-To: [EMAIL PROTECTED]
R. Knauer wrote:
> On Fri, 12 Feb 1999 05:56:40 GMT, Dave Knapp <[EMAIL PROTECTED]> wrote:
>
> >A random uniform generator is what you are looking for.
>
> That's a bit circular, isn't it?
>
> And the digits in Champernowne's number are almost uniform with regard
> to bit groups, yet it is hardly a candidate for a TRNG.
>
> I like the term "equiprobable" because it imparts the concepts of
> independence and equidistributed in one word. I believe independence
> and equidistributed are sufficient for a crypto-grade TRNG.
>
> Independence means there are no correlations and equidistributed means
> there is no bias. Numbers that have no bias or correlation cannot be
> predicted, which means they are proveably secure for use in crypto.
>
> Bob Knauer
>
> "The one thing every man fears is the unknown. When presented with this
> scenario, individual rights will be willingly relinquished for the
> guarantee of their well being granted to them by their world government."
> --Henry Kissinger
Actually independence is stronger than non-correlated. The example of the
binary Champernowne number shows that bias may go to zero rather slowly
(1/logN). Independence is certainly necessary. No bias, and the proper rate
of fluctuation is also necessary.
Tony
------------------------------
** 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
******************************
