Cryptography-Digest Digest #258, Volume #9 Sun, 21 Mar 99 02:13:04 EST
Contents:
Re: Splitting privtae keys (Scott Fluhrer)
Re: a little math please (Thomas Pornin)
Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED (wtshaw)
Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED (wtshaw)
Re: Testing Algorithm (hash) (David A Molnar)
Re: Splitting privtae keys (wtshaw)
Re: SHS (Sha) (wtshaw)
Looking for raw computer security data (shahid mustafa)
Re: pRNG that is "predictable to the left"? (Scott Fluhrer)
Re: a-8d~0.2844.5k:-89y ("Douglas A. Gwyn")
IDEA algorithm ([EMAIL PROTECTED])
Re: Random Walk ("Douglas A. Gwyn")
Re: Telephone Encryption (Mike Markowitz)
Re: dongle, encryption (William A Moyes)
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Newbie, what a stupid term... (Brandt)
----------------------------------------------------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Splitting privtae keys
Date: Sat, 20 Mar 1999 23:21:56 GMT
In article <7d17q0$imf$[EMAIL PROTECTED]>,
David A Molnar <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] wrote:
>> I am trying to find a way to divide a large private key (e.g. 1024 )
>> into one large piece and another small piece (e.g. 128), such that the
>> owner of the key holds the small piece, and some other party holds the
>> large piece. When the key is needed, the 2 pieces are recombined on the
>> owner machine to a complete key.
>
>> Does anybody know any algorithms which perform such an operation?
>
>There are several secret sharing schemes which would satisfy the
>requirement that a key can be broken into 2 pieces and later recombined.
>Applied Cryptography 2nd ed sec 23.2 gives three of them - Adi Shamir's
>scheme using polynomials, George Blakely's vector-based scheme, and
>a scheme with matrix multiplication and another that uses a prime field.
Actually, if you require *all* the pieces be submitted to reconstruct
the original secret (key), then there's an easier way: give one party a
random string, and the other party the xor of the secret with that random
string. To reconstruct, just xor the two shares together.
If the size differential is too large to make this practical, then you
can pick a symmetric encryption algorithm (eg. DES), make the small piece
a random DES key, and the large piece the real key encrypted with that
key.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: a little math please
Date: 21 Mar 1999 01:02:59 GMT
According to <[EMAIL PROTECTED]>:
> Thanks a lot. I just needed to know. BTW, how did you calc that? (what
> program?)
maple. On a Solaris sparc. But a mere "dc" with a shell script would
have done the job.
--Thomas Pornin
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Date: Sat, 20 Mar 1999 19:09:39 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
> > In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
> > <[EMAIL PROTECTED]> wrote:
> > > If I were king, nobody would be allowed to work on creating crypto
> > > systems until after he has cracked several really tough ones.
> > You present too high a barrier. It is best to promote thought in all
> > areas of crypto than to limit people to following in someone else's wake.
>
> I didn't suggest that future cryptosystems necessarily ought to be
> based on past ones. However, they certainly ought to avoid the
> *weaknesses* of past ones. The only way I know to obtain a good
> appreciation for the weaknesses is to discover them for yourself.
If you can learn from your mistakes, that is one way, but you need not
make all mistakes to appreciate that some can be fatal ones. Nor, do you
have time in this lifetime to replicate all past efforts in cryptology,
although I have felt that was what I had led myself into a time or two.
We suppose that the press of battle being absent, the risks of failing are
somewhat diminished. I enjoy learning how to break ciphers, but one could
chose to do nothing else. Enjoyable as that is, I know that, again, time
does not allow that option. It is refreshing to remember breaking a few,
even without formal help at the time; that may have been a deeper
beneficial experience than I thought it was, I cannot judge that to be
necessarily so.
--
Security that is more an allusion than a delusion is nevertheless probably still
insufficient; but, fooling your opponents may prove easier than convincing them of the
truth.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: The Magic Screw, Non-Secret Encryption, and the Latest WIRED
Date: Sat, 20 Mar 1999 19:20:05 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> John Savard wrote:
> > "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote, in part:
> > >... If I were king, nobody would be allowed to work on creating
> > >crypto systems until after he has cracked several really tough ones.
> > But that might leave us bereft of possible solutions -
>
> What sort of "solutions" would they be if the designers didn't know
> how they could be successfully attacked?
There is justification for someone trying to break a cipher they have
created, since the originator is often apt to understand it earlier and
deeper than anyone else. If something falls quickly, the temptation is to
not speak of it, but of a new and improved version, if any, that counters
a known weakness in a prior design.
Room exists to design some ciphers, if only scaled down ones, that might
be attacked. So, we could return to an old thread about the usefulness of
scalable ciphers, types of ciphers I personally like to explore (many
lines of ciphertext examples cheerfully excluded).
--
Security that is more an allusion than a delusion is nevertheless probably still
insufficient; but, fooling your opponents may prove easier than convincing them of the
truth.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Testing Algorithm (hash)
Date: 21 Mar 1999 01:38:32 GMT
[EMAIL PROTECTED] wrote:
> Well I hope my mother will pick it up for my 17th (April 7th :) ). It seems
> kinda nerdish, but hey it's what I like :)
Tell me about it. In my case it was my sister and my 15th. :-)
Don't worry too much about the nerdish part - pretty soon you'll be past
caring. :-)
> BTW, is that book really that good? I have only heard good things about it,
> which is why I want to get it. Is there anything I should know about it
> first? (Any errata?)
http://www.counterpane.com/ac2errv30.html
has the errata for the 2nd edition. Some of them look minor, but errors
in subscripts in source code or algorithm descriptions are no fun.
It really is "that good" - but there are a few areas that it doesn't
cover, or doesn't cover in much depth.
This may be because such areas are still up in the air (there is no discussion
of random oracles), weren't developed when the book was last updated
(chaffing and winnowing, all or nothing transforms, lattice cryptosystems),
or would require more complexity theory/math than is developed in the book
(exact security, precisely deliniating all classes of problems which have
randomized proofs/interactive ones).
None of this should count against the book; just you need to be aware that
comprehensive as it is, it is not the final word. In particular, if you
end up wanting to follow recent academic papers, you'll need to develop
a better understanding of things like probabilistic encryption. Fortunately,
many of the relevant articles are available on the Web for free. :>
Plus there aren't too many proofs, but that's why it's _Applied_ cryptography.
Probably none of that will matter so much for a while, though.
-David
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Splitting privtae keys
Date: Sat, 20 Mar 1999 19:32:55 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> I am trying to find a way to divide a large private key (e.g. 1024 )
> into one large piece and another small piece (e.g. 128), such that the
> owner of the key holds the small piece, and some other party holds the
> large piece. When the key is needed, the 2 pieces are recombined on the
> owner machine to a complete key.
>
> Does anybody know any algorithms which perform such an operation?
Divide may be the wrong technique, as any number of algorthms could be
used to encrypt the greater part of your large private key taken as
plaintext with the lesser one, a key in such a process. You could make
this an obscure process, but it could not be used in a widespread manner.
In a pure division of the key, the keylength is proportional to the size
of the key. So, you give the smallest chuck of it to the person most apt
to try to break the whole key.
There is an alternative method in which two or more parts, each as long as
the original key, might be combined to produce the original. There are a
number of protocols to handle different situations regarding how many can
be involved and who is necessary to reconstitute the original key.
--
Security that is more an allusion than a delusion is nevertheless probably still
insufficient; but, fooling your opponents may prove easier than convincing them of the
truth.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: SHS (Sha)
Date: Sat, 20 Mar 1999 19:44:40 -0600
In article <7d0tra$r37$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> that's the one. The problem is I can't read the sub-script text. If anyone
> has a .TXT translation I could use that.
>
Although it is status to use highly formatted documents, the LCD of
readable information should be a simple textfile. And, for similiar
reasons, HTML should be in the lowest version if possible. Otherwise, you
are forcing people to use newer forms of programs when it is absolutely
unnecessary.
Unless specifically unavoidable, I will always read with an old generic
program that includes minimal functions, including Mosaic for the www. If
security is our big concern, we should be about preserving the fundamental
tried, and true, with as few unknowns as possible.
--
Security that is more an allusion than a delusion is nevertheless probably still
insufficient; but, fooling your opponents may prove easier than convincing them of the
truth.
------------------------------
From: shahid mustafa <[EMAIL PROTECTED]>
Subject: Looking for raw computer security data
Date: Sat, 20 Mar 1999 22:10:58 -0500
I am looking for sites which may have computer security related raw
data. I need this data badly for my dissertation. This is my first
time on this newsgroup. Could someone point me out to sites which have
computer security statistics.
Thanks,
Sami Mustafa
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: pRNG that is "predictable to the left"?
Date: Sun, 21 Mar 1999 04:47:22 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] ("Steve Myers") wrote:
>Scott Fluhrer wrote in message <7cuog9$[EMAIL PROTECTED]>...
>>
>>As a counterexample, consider the generator:
>>
>> X(n+1) = SHA( X(n) )
>>
>>where "SHA" is a one-way function (not necessarily the Secure Hash
>>Algorithm).
>>
>>Now, this generator is predictable to the right (one way functions are
>>easy to perform, by definition), but unpredictable to the left (one way
>>functions are hard to invert, by definition).
>
>
>This is not hard to predict because secure hashing gives you nothing about
>unpredictability, if I take any
>SHA and produce SHA' s.t. SHA'(x)= 00000||SHA(x), where || is the
>concatenation operator, then SHA' remains secure as a
>hash function, where presumably you have some strong collision resistance
>property that SHA needs to satisfy in order to be secure.
>Now, if you see a string 0000 from the left, then predict the next bit is
>0, and you will be correct with a pretty high probability (I'm assuming that
>SHA already does not produce a lot of strings of the form 0000 for random x,
>which could be formalized, but I won't take the time).
You're right. One-wayness by itself does not, guarantee unpredictability.
However, if you tighten up the definition, making a few additional conditions
on top of one-wayness to prevent such pathological conditions, you should get
the result. I could formalize these additional conditions, but I won't take
the time :-)
>
>Defn of pseudo-random (extreme intuition, poor formalism) there exists no
>(non-uniform) infinite family {C_n} of poly sized circuits, which can
>distinguish between a random input, and the result of a pseudo-random
>generator on a random seed with probability >= \frac{1}{n^c} for all
>constants c, and sufficiently large n.
>
>Proof Sketch (Presumably the only semi-interesting Direction)
>G is not pseudo-random=> G is not predictable from the left.
I think you meant:
G is not pseudo-random=> G is predictable from the left.
And, as the proof is equally valid in the other direction, I'll make it:
G is not pseudo-random=> G is predictable to the left.
[Valid proof snipped]
So, what's going on here? I have demonstrated a (not pseudo-random)
sequence that is unpredictable to the left, and you have a proof that
non pseudo-random sequences are always unpredictable to the left.
Well, it's actually quite simple: we're using slightly different
definitions for predictability.
In my definition, the predictor gets to look at N outputs from the
generator (where each output is an M bit output from the generator),
and attempt to predict the previous output (with nontrivial
probability of success).
In your definition, the predictor gets to look at N bits from the
generator and attempt to predict the previous bit (with nontrivial
probability of success).
The distinction? In my definition, the predictor is not allowed to
examine the bit sequence anywhere he cares to -- he has to look at
it at an output (M bit) boundary. In your definition, the predictor
is allowed to examine it anywhere he cares to.
So, by your definition, my sequence is predictable, because if the
predictor examines M-1 bits from X(n), and M bits from the X(n+1),
the two possibilities for the previous remaining bit from X(n) can
be tested quickly. Of course, by my definition, this sort of
attack is not allowed -- the predictor gets all the bits of X(n) or
none of them.
So, it looks like we're both right (it just depends on the attack
model) :-)
--
poncho
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: a-8d~0.2844.5k:-89y
Date: Sun, 21 Mar 1999 05:03:09 GMT
hapticz wrote:
> i still don't believe it is possible to walk on water or all the other bullsht.
Sure it is, and since iced-over lakes are almost never seen in the
Middle East, if one did occur it would sure seem to be a miracle.
------------------------------
From: [EMAIL PROTECTED]
Subject: IDEA algorithm
Date: Sun, 21 Mar 1999 05:04:03 GMT
I found an IDEA source (may be old, at
http://rschp2.anu.edu.au:8080/idea.html) and I have 2 questions.
1) Are multiplications suppose to be mod 65537?
2) Given Ax = B, how do you calculate the multplicative inverse of A?
Should it not be A = Bx? It says:
sXX* = Mutiplicative inverse of sXX
sXX# = Additive inverse (this is just a sign flip right?)
Thanks,
Tom
btw, I will be adding IDEA to my public domain crypto lib.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Sun, 21 Mar 1999 05:23:14 GMT
"R. Knauer" wrote:
> >> There is no statistical test to decide if a keystream is crypto-grade
> >> random. Therefore ALL applications of statistical tests for that
> >> purpose are inappropriate and their results misinterpreted.
That's wrong. Statistical tests, properly applied and administered,
can provide information useful in judging the likelihood of various
properties of a sequence.
The claim that cryptographic security requires a truly random
physical process is also wrong. Actual military-grade systems
don't normally incorporate "true" (physical) randomness, yet
they have proven quite secure, for example not having been
broken (so far as is known to the US) for several decades.
Even the old electromechanical SIGABA wasn't broken during its
long operational lifetime.
There are measures of cryptosecurity, such as required work
factor to recover a certain expected fraction of the plaintext
information a certain expected fraction of the time. With
some designs, this can be reliably estimated.
The main problem with the notion of using physically random
key streams is the coordination required between sender and
receiver. If one of them generates the key and sends it to
the other, to maintain security nearly as much key material
is needed to send the key as is being sent. The alternative
is to transport the key via secure physical means, such as
armed courier. This isn't very practical compared to the
*highly secure* non-physically-randomly-keyed cryptosystems
actually in use.
------------------------------
From: [EMAIL PROTECTED] (Mike Markowitz)
Subject: Re: Telephone Encryption
Reply-To: [EMAIL PROTECTED]
Date: Sun, 21 Mar 1999 05:41:45 GMT
"Roger Schlafly" <[EMAIL PROTECTED]> wrote:
>
>R. Knauer wrote in message <[EMAIL PROTECTED]>...
>>Did the Clipper Chip ever implement the trapdoor or other means of
>>defeating it that the govt wanted? IOW, is the current version of the
>>Clipper Chip secure?
>
>The chips are now called "Fortezza". They no longer have the
>"Law Enforcement Access Field" that was so controversial.
Technical corrections:
"FORTEZZA" (all caps!) is the *PCMCIA card* containing a *Capstone*
chip (a.k.a. an MYK-80). (The LEAF was removed, but private KEA keys
are still escrowed.)
OTOH, "Clipper" refers to the chips MYK-78E, MYK-78T, MYK-77. These
implement only Skipjack (http://www.rainbow.com/mykoweb/myk78E.htm),
while "Capstone" adds KEA.
The MYK-77 through MYK-80 are based on an ARM6 core. (There's also now
an ARM6-based MYK-82 (http://www.rainbow.com/mykoweb/myk82.htm) and an
ARM7-based MYK-85 that adds D-H and RSA
(http://www.rainbow.com/mykoweb/myk85.htm).
-mjm
------------------------------
From: [EMAIL PROTECTED] (William A Moyes)
Subject: Re: dongle, encryption
Date: 21 Mar 1999 05:56:58 GMT
DOREL Verlags GmbH & Co. KG ([EMAIL PROTECTED]) wrote:
: Hello!
: Does anyone have experience with hardware dongles and their particular
: encryption methods?
: I want to find out which type of dongle resp. the encrytion method used
: would be the saved way to protect software against unauthorized using it.
: Each manufacture claims to have the best and savest protection method. :-|
Depends upon the manufacturer. Many have none, some use DES, many
use custom algorithms.
-William Moyes
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 21 Mar 1999 06:00:35 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: Brandt <[EMAIL PROTECTED]>
Subject: Newbie, what a stupid term...
Date: Sat, 20 Mar 1999 23:31:42 -0500
I would like to know the best place to start to learn
cryptography. To learn the the vocab and the math skills. Also
where to learn the concept of Unix password encryption. I do not
understand if there are random characters introduced, how does it
come out the same when the server compares the resulting hash? I
know two of the same passwords will not look the same. Well a
simple as possible answer would be nice. Please use sinple
terms too.
Thanks Miles800. Please reply to [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
******************************
