Cryptography-Digest Digest #274, Volume #10 Sun, 19 Sep 99 14:13:02 EDT
Contents:
Discrete Logarithm Signatures? (Tom St Denis)
peekboo source (Tom St Denis)
Re: Okay "experts," how do you do it? (David A Molnar)
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Re: (US) Administration Updates Encryption Export Policy (Dmitri Alperovitch)
Re: Discrete Logarithm Signatures? ("Richard Parker")
PART B. ANALYSIS AND BREAKING OF BRAUN'S CRYPTO V3.5 (JPeschel)
Re: Mystery inc. (Beale cyphers) ([EMAIL PROTECTED])
Re: Exclusive Or (XOR) Knapsacks ("rosi")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Discrete Logarithm Signatures?
Date: Sun, 19 Sep 1999 12:08:35 GMT
I want to add a sign/verify feature to my public keys panel in PeekBoo. I
have read Applied Cryptos section on it, but there are some things I don't
quite get...
It has a table of them (Table 20.5 on page 497), I will take the first for
example
Sign: r'k = s + mx mod q
Verify: r^(r') = g^s * y^m mod p
I just want to get the variables straight...
r is g^k mod p (k is the random secret variable)
r' is ? (inverse mod p?)
s is ?
m is the hash right?
y is the public key right?
if p-1/2 is prime can I use that directly for q (q = p-1/2)?
--
Anyways, if you haven't tried peekboo yet it's at
http://www.cell2000.net/security/peekboo/peekboo.exe
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: peekboo source
Date: Sun, 19 Sep 1999 12:21:20 GMT
Peekboo source can be found at
http://www.cell2000.net/security/peekboo/pb_backup.zip
(it's my current source backup of v1.4)
If people could hack at it, find bugs, find security flaws (i.e bad dh math?)
I would appreciate it. If you just want to snoop thru the code it's there.
You will need lcc-win32 to build it though...
The current binary is at
http://www.cell2000.net/security/peekboo/peekboo.exe
Tom
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Okay "experts," how do you do it?
Date: 19 Sep 1999 14:14:20 GMT
[EMAIL PROTECTED] wrote:
> : > You don't count many mathematicians among your friends, do you?
> : Are you referring to [EMAIL PROTECTED] or to my response?
> Your response. A criticism was not intended: simply a statement that all
> mathematicians "think that way" - although usually, only when appropriate,
> for determining solvability in a theoretical sense, and they do also
> realize that some problems are not solvable in practice due to time
> constraints.
Oh. Thanks for clarifying! The friend in question is indeed a math/physics
major, so calling her a "mathematician" is probably not too far off. :-)
I had not really thought about the difference in attitude before
explaining RSA and being met with "but how is this secure, since N and the
factors of N are equivalent information?"
but yes, she also knew that factoring was hard. Just didn't think about it
at first.
Thanks,
-David
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 19 Sep 1999 05:00:36 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: [EMAIL PROTECTED] (Dmitri Alperovitch)
Subject: Re: (US) Administration Updates Encryption Export Policy
Date: Sun, 19 Sep 1999 14:38:02 GMT
>Anthony Stephen Szopa wrote:
>> 3) If this is anything to be concerned about then tell me, has the
>> US government withdrawn its appeal in the Bernstein case? I doubt
>> it because the government is not sincere and full of beans.
>
>No doubt, the government is healthy (full of beans). :-)
>
>The Bernstein case is a different matter. If in fact Bernstein was
>in violation of a law that was current when he violated it, then a
>later change in the law does not prevent prosecution for the earlier
>crime, unless the new law specifically states that (which is rare).
>But it seems we're now talking about an administrative policy, not
>a law.
Apparently, it is still illegal to export source code without a license.
The BXA page points out that the new policy is for object code only.
Regards,
Dmitri
[EMAIL PROTECTED]
------------------------------
From: "Richard Parker" <[EMAIL PROTECTED]>
Subject: Re: Discrete Logarithm Signatures?
Date: Sun, 19 Sep 1999 14:56:49 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> r' is ? (inverse mod p?)
The variable r' is defined as r' = r mod q, where r = g^k mod p.
> s is ?
Together the numbers r and s are the signature.
> m is the hash right?
Correct. The variable m is the message that you want to sign, which
in a practical implementations is a hash of the true message.
> y is the public key right?
Yes. It is defined as y = g^x mod p.
> if p-1/2 is prime can I use that directly for q (q = p-1/2)?
Yes, if (p-1)/2 is prime it is a large prime factor of p-1, and thus a
candidate for q. However, since p should be at least 1024 bits, q
will be 1023 bits long. A q with this many bits complicates the
computations involved in signing and verifying.
-Richard
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: PART B. ANALYSIS AND BREAKING OF BRAUN'S CRYPTO V3.5
Date: 19 Sep 1999 15:46:05 GMT
Part B of Casimir's essay is now up my site.
Source code for a cracker will be up shortly.
Anyone else care to try their hand at cracking
this baby?
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Mystery inc. (Beale cyphers)
Date: Sun, 19 Sep 1999 16:01:52 GMT
In article <19990918124924.449$[EMAIL PROTECTED]>,
> Niteowl <[EMAIL PROTECTED]> wrote:
> > Dr. Matyas wrote a paper after much apparent research and thinks the
> > version of the DOI used was from "An Historical, Geographical,
> > Commercial, and Philosophical View of the American United States"
> > published in 1795 by W. Winterbotham. The version of the DOI there
> > does 'correct' many of the numbering errors seen in B2.
I compared Dr. Matyas' copy of the Winterbotham DOI to the version
in doi.doc. As far as B2 is concerned, the only significant difference
occurs at position 519 where "meantime" is spelled as two words instead
of one word. Since Beale's numbers are already off by +10 at that
point and are off by +9 after this point, separating meantime into two
words doesn't provide much of a correction to the document as a whole.
It does suggest that in whatever document Beale was using, meantime was
printed as two words, but that is hardly enough to prove that
Winterbotham's document was the one used by Beale.
There were other differences that would not have effected the
numbering in B2. Some words such as "time" at position 639 are spelled
with plural endings, i.e. "times". Some of these differences are
already noted in doi.doc. I also found "shown" at position 205
spelled as "shewn" by Winterbotham. Plural endings would affect letter
counts, but not word counts.
[EMAIL PROTECTED] (Curt Welch) wrote:
> So I guess this means that Dr. Matyas examined many different versions
> of the DOI and _only_ that publication was found to contain a version
> of the DOI which so closely matched the errors?
I don't think that Winterbotham's DOI is a better match in any
significant sense. I think that Matyas applied other criteria, such
as "availability". Winterbotham's book would have had a wide
circulation and would thus have been more likely available to Beale in
1822, compared to the other DOI's that Matyas found.
Matyas published a booklet in 1996 titled, The Beale Ciphers, which
contained the Winterbotham document and Matyas' own Cipher Table
theory. This was available from him directly by writing to:
Dr. Stephen M. Matyas
25 Valkill Drive
Poughkeepsie, NY 12601
I no longer know the exact price he was charging.
> I actually find it surprising that anyone would publish a modified
> version of the DOI. Do you know what the differences were (in the
> 1795 publication) and have any understanding of why it was changed?
> i.e., just sloppy work (typos etc) or some type of intentional
> editing?
As far as the 1795 publication, the differences are noted above.
Actual word changes seem to be fairly rare, as you would expect for
such a document. The most common source of variant DOI's are those
that have been shortened to fit into available space. I see one of
these every 4th of July in the local newspaper. The editors feel
patriotically bound to publish the DOI on this date, but not all of it,
presumeably because of the limited amount of space on the editorial
page, where it usually appears. Such editing makes it possible to
account for numbering differences without assuming that Beale himself
made counting errors.
-- Jeff Hill
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Exclusive Or (XOR) Knapsacks
Date: Sun, 19 Sep 1999 13:12:24 -0400
Dear Trevor,
Thank you so much for the post and especially the last question, which is
the most important of all to ask.
I think you are right. The only little thing I want to make a bit more
concrete
is that the 'bit selection' (or whatever one design that to be to give such
properties) is secret and not really secret. This statement may appear to
be confusing and contradictory, but let me develop it a bit further (just so
that
other people does not get confused by me).
This is a general approach that may be applied to all ciphers. It is
message
dependency. One thing obvious to us is that the message from the encryptor
is _secret_ (or else we wouldn't have to waste our time here). Not to
utilize that
may be a waste. As to particular types of schemes (MH for one), the
piecemeal
decryption can be an advantage. A simplistic heuristic reasoning: if an
attacker
can also do it piecemeal (e.g. gain 100% confidence of a bit without knowing
other bits in poly time), then we can stop right here. This is the
assumption that
we take.
Therefore, if the decrytpor, after gaining knowledge of certain bits can
disentangle the being processed subset sum in some particular way, the
decryption proceeds toward the desired goal. However, if an attacker does
not have the capability of doing this, he has to proceed to a subset sum
solution and then verify if the whole thing makes sense. As I said, if there
are many, many subset sum breakdowns, we can easily see the difficulty
for the attacker. A few points.
1. Pertaining particularly to lattice reduction, a solution has a very
short
corresponding vector. As many anticipate that such a vector is
'overwhelmingly'
shorter than the next short one in the lattice. Now if there are many, many
subset
sum breakdowns, all these corresponding vectors are very close in length. In
fact,
the actual solution vector may not even be the shortest.
2. There is no other 'description' for the problem, except 'subset sum'
as far
as I now. Therefore, no other ways of attacking is existent (I can be wrong
and
this is only an ASSUMPTION. There is NO provable security. NONE. PERIOD)
3. As the additional 'complication' depends on the message or plaintext,
the 'addition of the structure' need not be secrect. An attacker can be
given
the method of such addition, but with no definitive knowledge of the message
or plaintext (which much be a given, else all we talk here is nonsense), can
get little help. This can only help him verify if a subset sum breakdown
is the right one, but only after he gets such a breakdown. In addition,
flexibility
can be built in so that, this addition can be different for different
instances of
encryption. It can also be kept secret. As the decoupling of this piece of
information from the major portion of the key(s) provides the flexibility,
there is
this mode that I call semi-secret. In case the piece of secret is
compromised,
security does not face disaster. But again, this piece can be
session/encryption
specific (as a session key).
4. This can be made truly 'complete' where detectable 'garbabe
ciphertext'
(blocks) can be sent. The encryptor with very high probability can detect
(with no
assumption of the syntax or semantics of the underlying message) and there
can
be ways to guarantee the detection (with no loss of security of the basic
scheme).
There can be other properties and other ways of designing it, I hope.
Lastly, to answer your question at the end (which I did in some way in
item
2). I do NOT know how difficult. Only that it appears to me to be difficult
(as
it is much closer to a generic subset sum problem: Given a (finite) set of
integers S and another integer x (both arbitrary), determine if x is a
subset
sum of S).
--- (My Signature)
P.S.
By 'many, many', I do not mean hundreds or thousands, but many more.
I have been talking about trapdoor one-way not uninvertible one-way
in this message. Sorry I deviated from the original post if that intends to
talk about the latter.
Trevor Jackson, III wrote in message <[EMAIL PROTECTED]>...
>rosi wrote:
>
>> Trevor Jackson, III wrote in message <[EMAIL PROTECTED]>...
>> [Snip]
>> >
>> >Does the non-unique case permit extension to the point that uniqueness
may
>> be
>> >provided by additional information? I.e., could a "key pair" be created
>> such
>> >that the "public" portion is non-unique, perhaps in pathologically so,
>> while the
>> >"private" portion determines the unique solution?
>> >
>>
>> Yes and No depending on a couple of things.
>>
>> Additional information, yes.
>> Private, not necessarily. If private, it is analog to keeping a
'subset'
>> bits of an
>> RSA modulus secret. (Nonetheless, keeping it secret does in no way, I
hope,
>> decrease the security or the complexity for an attack)
>>
>> The property of 'non-uniqueness' (note in quotes) is provided by
>> 'structure'
>> rather than secret information (but of course the private key is still
>> secret).
>>
>> A bit more (only in the limited one-way trapdoor sense this time).
Say, A
>> and
>> B are to perform the treat with a set {1, 2, 3, 7, 19}. If the subset sum
is
>> 10,
>> well that is beyond NP-complete. An attacker can NOT get it (i.e. 1+2+7
or
>> 3+7?). Call it Perfect Secrecy? A bit of flavor. However, non-unique in
this
>> true sense does not give us any ease. The decryptor can not get it,
EITHER!
>> If the decryptor winnows out undesirable ones taking advantage of any
>> additional characteristic of the message, or any other additional
>> information,
>> we go back to square one. That is, whether that 'piece' is to be kept
>> secret.
>> However, to be brief, if one designs it in such a way that the solution
can
>> be
>> unique (which IMHO can be achieved in more than one way with different
>> ease for A and B, and no less complexity for the attacker) to the
decryptor
>> (_AND_ the encryptor), but as a subset sum it can really decomposed in
>> more than one way. The simplest is to consider the above example. If one
>> can design it in a way that only one of 1+2+7 and 3+7 can be valid, the
>> point
>> may be clearer.
>>
>> Finally, I think, when we talk about security, etc. we re-visit the
same
>> set
>> of questions, which are many and can get us very 'involved' and sometimes
we
>> can not put a satisfactory stop to it once started. The questions are
very
>> straightforward, independent of math formulae and so forth. Take this for
>> an example, what one does is to look hard at the way A and B does the
>> treat and the way(s) (any imaginable ones) an attacker can institute. No
>> doubt, one can not cover all. But if one thinks in generic terms, he is
>> likely
>> to cover a large area. One thing obvious to me --- and I believe to
all ---
>> is that A or B does the decryption treat piece meal while the attacker
>> 'cannot'. When such a difference is 'distilled and enlarged' (If you have
>> 4-5, you DO HAVE 4-5), ... Needless to say that both the cryptographer
and
>> the cryptanalysist need to look at any assumption harsh and straight in
the
>> eye
>> and avoid getting intoxicated in the (seemingly) success they (maybe
>> temporarily) get.
>>
>> Thank you so much Trevor.
>> --- (My Signature)
>>
>> P.S.
>> Think saying a bit more here won't hurt (about 'unique'). It is, IMO,
>> possible
>> that the public portion at publication is semantics dense (or in other
>> words,
>> an attacker gets the 1+2+7 or 3+7 situation). However, if all the secret
is
>> one-sided, I can not think of a way to really create the situation for an
>> attacker while A and B do not get confused at all. It is quite against
>> intuition,
>> but I can be wrong. One day, somebody may come up with this Perfect
>> Secrecy, but I doubt. Therefore, if A and B are to perform the treat, at
>> some
>> point, more needs to be revealed in one way or another. I just would like
to
>> emphasize: I have no appetite to bet my life (or any portion of it) on
PS. I
>> ONLY strive for one-wayness. If any is in the same frame of mind, we are
>> in the same camp. I am in no way saying 'shut up' to anybody. I have no
>> right to do so in any fashion. I lay down my scope so that other people
and
>> I talk in the same terms. (BTW, I gave my def. or my version of trapdoor
>> one-
>> way)
>
>Thank you for the thoughtful response.
>
>It appears that a pathologically dense collection could be publicly
defined, and
>a secret bit vector selected that indicated a subset with the uniqueness
>property (i.e., it does not add to the public collection, but subtracts
from
>it).
>If the number of such unique subsets were large, which should be the case
for a
>pathological collection, it would be difficult for an attacker to identify
the
>particular subset.
>
>How difficult?
>
>
------------------------------
** 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
******************************
