Cryptography-Digest Digest #984, Volume #11 Fri, 9 Jun 00 08:13:01 EDT
Contents:
Re: Some dumb questions (Mok-Kong Shen)
Re: Some dumb questions (Mok-Kong Shen)
Re: testing non linearity of arithmetic-logic combinations (Mok-Kong Shen)
Re: My lastest paper on Block Ciphers (Mark Wooding)
Re: Random IV Generation (Mok-Kong Shen)
Re: Cryptographic voting (Mok-Kong Shen)
Re: Cryptographic voting (Mok-Kong Shen)
Re: ZKPs in practice? (Mark Wooding)
Re: PK analogue for passwords (Daniel James)
Re: My lastest paper on Block Ciphers (tomstd)
Re: testing non linearity of arithmetic-logic combinations (Klaus Pommerening)
Re: My lastest paper on Block Ciphers (tomstd)
Re: Random IV Generation (tomstd)
re: my latest paper (tomstd)
Re: Cryptographic voting (Mark Wooding)
Re: Random IV Generation (Mark Wooding)
OT: Starmath font (tomstd)
Re: equation involving xor and mod 2^32 operations (Guy Macon)
Re: Is OTP unbreakable?/Station-Station (Guy Macon)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Fri, 09 Jun 2000 12:19:57 +0200
Jim Gillogly wrote:
> Mok-Kong Shen wrote:
> > Jim Gillogly wrote:
> > > ... use a kappa test: slide the two
> > > ciphertexts against each other and count the number of coincidences
> > > at each offset ...
> >
> > I guess that flattening the frequency distribution with some appropriate
> > techniques would provide sufficient immunity to such techniques.
> > Further, if OTP is employed two times, it's likely, in my view, that the
> > use of two same or overlapping segments are done at widely separate
> > timepoints and therefore the pool of messages containing these is quite
> > large and hence the chance of hitting such favourable pairs is
> > correspondingly low, I suppose.
>
> "Some appropriate techniques" are not obvious, and "sufficient immunity"
> will presumably depend on the value of the data. For example, simply
> doing a Vigenere with key COMERETRIBUTION or MANCHESTERBLUFF will flatten
> the distribution, but will still fall apart if the coincidence is checked
> at varying offsets. In addition, it's normally not safe to assume the
> widely separate times and large number of messages will save you. Consider
> again VENONA as a counterexample. Comparing each pair of messages is an
> N^2 problem, granted, but each test is cheap and the potential payoff is
> enormous: you've gotten a peek into the enemy's most secret traffic.
>
> As Robert Morris (pere) said (paraphrased from memory), "Never underestimate
> the amount of time, money, and effort an opponent will expend in order to
> read your traffic."
I appreciate very much your comments and agree with you. Also your
citation is valuable. On the point of details of 'better techniques' to
flatten the frequency distribution (though, as I explained previously,
is not of primary importance in the present discussion) I do like, just
for the purpose of learning some other opinions, to say that I guess
that transposition plus polyalphabetic substitution (at the byte level)
plus random cyclic bits rotations of computer words could make a
quite good viable candidate, though it may not be always justifible
from other viewpoints, e.g. operating expenses/difficulties. (To
avoid flames from other readers due to misunderstanding, let me
repeat that I don't 'recommend' or 'propose' using n-OTP with
frequency flattening as desciribed above and that I am in fact not
even sympathetic to OTP as such.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Fri, 09 Jun 2000 12:20:05 +0200
Volker Hetzer wrote:
> IMHO the explanations you've got so far (from others and (hopefully) me)
> should get you started thinking about an approach.
I appreciate very much everybody's, including yours, contribution to
this thread. (I asked you the last time the one question only because I
guessed that you probably had some ready and effective way of dealing
with the problem concerned but which was not apparent to some of us,
in particular to me.)
Cheers,
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: testing non linearity of arithmetic-logic combinations
Date: Fri, 09 Jun 2000 12:20:11 +0200
Terry Ritter wrote:
> With respect to nonlinearity, a completely random table is likely to
> be more nonlinear than an invertible substitution table which is
> necessarily restricted to be a permutation, but a random table is not
> guaranteed to be balanced, and is unlikely to be invertible.
> Similarly, a substitution table is likely to be more nonlinear than a
> similar-sized row or column of a Latin square which is more than just
> an arbitrary permutation: each row or column also must be a
> permutation in a set which will make a Latin square. Of course, a
> Latin square will have multiple of such permutations, each guaranteed
> different, so simply taking the minimum nonlinearity of all these
> measured one-by-one can be deceptive.
I have two additional dumb questions:
1. Consider two values X and Y in computer words. A mapping
that can't be expressed as X = a Y + b (mod 2^n), where
n is the number of bits in word, is non-linear, isn't it?
What is the (general) basis, i.e. principle, on which a
quantitative 'measure' of non-linearity is built on?
2. For a given n, the can be more than one n*n Litin square.
Are there quality differences among these as far as
crypto is concerned? If yes, how does one deal with that?
Thanks in advance.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: My lastest paper on Block Ciphers
Date: 9 Jun 2000 10:39:05 GMT
Sam Simpson <[EMAIL PROTECTED]> wrote:
> The "Starmath" font you use for mathematical symbols is not a
> standard font supplied with Windows/Office - perhaps you could either
> embed the font or use a portable document format (ps / pdf?).
I suspect that it's a StarOffice special.
Tom: Please take a look at LaTeX some time. There are good reasons why
it's still the de facto standard format for journal submissions in many
scientific fields, especially cryptography[1]. It's very good at
maintaining all the tedious bits of an article, like the section
numbering, lists of references and that sort of thing. Its mathematical
typesetting is unsurpassed (but takes a little effort to use properly).
There are good standard tools for producing PostScript and PDF files
from TeX output. And it's all free.
The LaTeX source for my Storin submission (in the source code archive)
is probably rather scary, but should give you a flavour for what's
possible. It's a shame more researchers don't publish their LaTeX
sources on the net.
Good books are available. You have to pay money for them, which is a
shame. Starting at the beginning: `The LaTeX2e Document Processing
System' by L. Lamport is the reference to LaTeX; `The TeXbook' by
D. E. Knuth describes the TeX system which lives `underneath' LaTeX (but
contains many details you probably don't need to know about; `The LaTeX
Companion' by F. Mittelbach et al. describes many of the extension
packages available, but to a large extent regurgitates freely-available
package documentation; `The LaTeX Graphics Companion' by S. Rahtz
is similar, and concentrates on graphical packages.
[1] There was a time when submitters were given no choice in the
matter. Nowadays Word documents are accepted, although almost
invariably grudgingly.
-- [mdw] --tex-grand-master
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random IV Generation
Date: Fri, 09 Jun 2000 12:49:00 +0200
Adam Durana wrote:
> [snip]
> ciphertexts. It wouldn't hurt to use a secure rng, but its not needed. The
> IV can even be made public.
I agree with your first sentence, but I think that it helps, if one can keep
the IV unknown to the opponent.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Fri, 09 Jun 2000 12:49:06 +0200
"Trevor L. Jackson, III" wrote:
> First, the Miranda decision is spelled that way. Second, I believe that
> citizens are required to identify themselves upon request, but are not
> required to produce identification of any kind.
I am just curious about how what you said in the second sentence is
realized and whether the underlying purpose (identification) can be
achieved at all in practice.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Fri, 09 Jun 2000 12:49:15 +0200
zapzing wrote:
> Surprisingly, I think I have come up with a protocol
> that will fulfill this requirement, to a certain
> extent, but it needs a trusted party to set it up.
>
> Say there are N voters. The trusted party (T) produces
> a large number of sets of N public/private key pairs.
> Each time an election is held, one set will be used up
> (in this sense it is like OTP). Each voter gets exactly
> one private key from the set, and each voter gets all
> the public keys.
>
> People broadcast their votes anonymously, they are
> encrypted with their private keys, and they have some
> sort of standardized header for identification
> purposes. After the votes are cast and everyone is
> sure all the votes have been seen, people broadcast
> anonymously their private keys. After that, anyone
> can claim they made any vote they want, and noone
> could know differntly, but everyone will know the
> outcome of the election.
>
> Unfortunately there is a vulnerable period between
> when people broadcast their votes and when they
> broadcast their public keys. I think this could
> maybe be fixed, but I'm not sure how.
>
> I would also like to get rid of T, but not
> sure how to do that either.
The point of trusted party is indeed the highly critical point. If the
existence of a trusted party can be assumed, then implementations
of voting schemes are feasible or even quite practical. If one
doesn't have that, I just can't yet imagine that a perfect voting
scheme can be constructed. (Note that the trusted party must
be in a position to identify you to be indeed who you claim to be.)
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: ZKPs in practice?
Date: 9 Jun 2000 10:47:48 GMT
Paulo S. L. M. Barreto <[EMAIL PROTECTED]> wrote:
> "David A. Wagner" wrote:
>
> > I believe Schnorr signatures have their roots in an efficient
> > zero-knowledge proof of identity. (Fiat-Shamir signatures, too.)
> > But I might have the details wrong -- it may be some notion related
> > to zero-knowledge, and not strictly speaking zero-knowledge, so don't
> > trust me here.
>
> Are you sure? Schnorr signatures are fundamentally based on the DL
> problem; in fact, there's hardly any difference between Schnorr and
> Nyberg-Rueppel signatures.
HAC, section 10.4.4 decribes an identification protocol due to Schnorr
very similar to his signature algorithm. It's not actually zero-
knowledge, but does have some useful properties.
-- [mdw]
------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: Re: PK analogue for passwords
Date: Fri, 09 Jun 2000 11:47:19 +0100
Reply-To: [EMAIL PROTECTED]
In article <8hoq4f$cuo$[EMAIL PROTECTED]>, wrote:
> if one is using twonz to keep their
> financialinstitution.com password secret, they would enter their pad in
> one text field, and financialinstition.com in the second text field, and
> the program would run the inputs through a hash function (probably md5
> since it is widely available on free unices) and then base64 encode the
> result, so one could type the whole thing without too much effort. :)
That sounds like a variation on the RFC1938 OTP scheme (perhaps it IS
RFC1938, if we don't take "base64 encode" literally).
I've seen a couple of implementations for that, but never heard of anyone
actually using it before.
Cheers,
Daniel.
------------------------------
Subject: Re: My lastest paper on Block Ciphers
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 09 Jun 2000 04:06:21 -0700
In article <[EMAIL PROTECTED]>, "Sam Simpson"
<[EMAIL PROTECTED]> wrote:
>The "Starmath" font you use for mathematical symbols is not a
>standard font supplied with Windows/Office - perhaps you could
either
>embed the font or use a portable document format (ps / pdf?).
>
>Apart from that, the paper is an interesting and generally well
>written piece.
>
I have never "embeded" a font before, but I will look into it.
Sorry about the mess.
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] (Klaus Pommerening)
Subject: Re: testing non linearity of arithmetic-logic combinations
Date: 9 Jun 2000 11:09:46 GMT
In <[EMAIL PROTECTED]> tomstd wrote:
> Anyways, a balanced sbox can be bent, take matsuis sboxes for
> example. Similarly CAST sboxes are bent.
>
A bent boolean map is definitely nonbalanced.
In particular a bent (perfect nonlinear) boolean function
F_2^n ---> F_2 has 2^{n-1} +- 2^{n/2 -1} zeroes,
a balanced function (by definition) 2^{n-1}.
But there are good approximations ("almost bent" + "almost balanced").
Search for papers by Pieprczyk, Seberry, Vaudenay, and Meier/
Staffelbach in the Proceedings of CRYPTO and EUROCRYPT.
Also a good reference is Josef Pieprczyk's book draft
http://www.cs.uow.edu.au/people/josef/
--
Klaus Pommerening [http://www.Uni-Mainz.DE/~pommeren/]
Institut fuer Medizinische Statistik und Dokumentation
der Johannes-Gutenberg-Universitaet, D-55101 Mainz, Germany
------------------------------
Subject: Re: My lastest paper on Block Ciphers
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 09 Jun 2000 04:09:04 -0700
In article <[EMAIL PROTECTED]>, Runu Knips
<[EMAIL PROTECTED]> wrote:
>tomstd wrote:
>> I have just finished the Draft of my latest paper. It's
called
>>
>> "On Cryptographically Strong F Functions"
>>
>> And is available (sorry) only in Word97 format at
>>
>> http://tomstdenis.com/ffunctions.zip
>>
>> There are probably tons of little mistakes, I have yet to have
>> anyone proofread it...
>>
>> I am open to critiques :)
>
>Tom, I have no time to really read your paper right now, only
>for a short look at it (content looks good), but if you would
>know how ugly the special characters of a candadian winword
>document look in a german winword you would have thought twice
>before using that format. I have the impression that these
>should be greek characters in the formulas but they aren't.
>They are really strange figures such as an inverted color <-
>or a small figure looking a little bit like @ etc. It's simply
>unreadeable, sorry.
>
Hmm well if I can figure out how to embed the font into the word
document I may be able to translate it to a portable format from
school. At home I can't access the site...
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: Random IV Generation
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 09 Jun 2000 04:13:31 -0700
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <mok-
[EMAIL PROTECTED]> wrote:
>
>
>Adam Durana wrote:
>
>> [snip]
>> ciphertexts. It wouldn't hurt to use a secure rng, but its
not needed. The
>> IV can even be made public.
>
>I agree with your first sentence, but I think that it helps, if
one can keep
>the IV unknown to the opponent.
You would have to send the IV securely which isn't always
possible, consider automatic communication relays of some
sort... you don't want to have to perform a RSA encryption for
small packets that occur often do ya?
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: my latest paper
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 09 Jun 2000 04:15:40 -0700
Ok I realize I made a silly mistake with pushing the paper in
Word97 format... so until I figure out the font situtation...
there at least is
http://tomstdenis.com/ffunctions.html
All the "center"ing I did is lost so some of the figures look
funny, but all the chars are there and it's better then nothing.
Once I figure out the font thing I will get a .PS copy out there.
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] (Mark Wooding)
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: 9 Jun 2000 11:24:45 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> zapzing wrote:
>
> > Surprisingly, I think I have come up with a protocol
> > that will fulfill this requirement, to a certain
> > extent, but it needs a trusted party to set it up.
> >
> > Say there are N voters. The trusted party (T) produces
> > a large number of sets of N public/private key pairs.
> > Each time an election is held, one set will be used up
> > (in this sense it is like OTP). Each voter gets exactly
> > one private key from the set, and each voter gets all
> > the public keys.
> >
> > People broadcast their votes anonymously, they are
> > encrypted with their private keys, and they have some
> > sort of standardized header for identification
> > purposes. After the votes are cast and everyone is
> > sure all the votes have been seen, people broadcast
> > anonymously their private keys. After that, anyone
> > can claim they made any vote they want, and noone
> > could know differntly, but everyone will know the
> > outcome of the election.
> >
> > Unfortunately there is a vulnerable period between
> > when people broadcast their votes and when they
> > broadcast their public keys. I think this could
> > maybe be fixed, but I'm not sure how.
> >
> > I would also like to get rid of T, but not
> > sure how to do that either.
>
> The point of trusted party is indeed the highly critical point. If the
> existence of a trusted party can be assumed, then implementations
> of voting schemes are feasible or even quite practical. If one
> doesn't have that, I just can't yet imagine that a perfect voting
> scheme can be constructed.
> (Note that the trusted party must be in a position to identify you to
> be indeed who you claim to be.)
This can be addressed easily using a cut-and-choose protocol. You
introduce a new phase into the overall system, where voters use their
private keys to obtain anonymous `voting tickets'. The system assumes
an anonymous broadcast medium; see Anderson's work on the `Cocaine
Auction Protocol' for more on this.
Here's how voting tickets might be issued. A voter, Alice, generates t
ticket requests Q_i = (V, R_i), where V is a fixed header, R_i is a
random number. She blinds each request using a different random secret
blinding factor, and submits them, in a message signed by her private
key, to the ticket issuing authority Bob. Bob picks one of the requests
j, and tells Alice his choice; Alice sends Bob her blinding factors for
all the requests except Q_j; Bob unblinds the requests and ensures that
they're valid (the random numbers are all different, the headers are
good, etc.). He then signs the remaining blinded request, confident
that it's valid, and returns it to Alice. Alice unblinds the signed
blinded request, and is left with a ticket, signed by Bob, which has an
identifying random number which only she knows.
There's some interesting work happening at IBM on voting systems. See,
for example, `A Secure and Optimally Efficient Multi-Authority Election
Scheme', by R. Cramer, R. Gennaro and B. Schoenmakers, at
http://www.research.ibm.com/security/election.ps
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Random IV Generation
Date: 9 Jun 2000 11:25:40 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> I agree with your first sentence, but I think that it helps, if one
> can keep the IV unknown to the opponent.
For CBC and CFB it can only protect the first plaintext block. I don't
think there's any point in keeping it secret.
-- [mdw]
------------------------------
Subject: OT: Starmath font
From: tomstd <[EMAIL PROTECTED]>
Date: Fri, 09 Jun 2000 04:30:35 -0700
You can get the starmath True Type Font off my website at
http://tomstdenis.com/files/starmath.ttf
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] (Guy Macon)
Subject: Re: equation involving xor and mod 2^32 operations
Date: 09 Jun 2000 07:45:19 EDT
One word of caution: Some programming languages don't implement MOD
the same way that it is used by mathematicians. Instead, they give
you the remainder after doing a division. Not the same thing.
This bit me in the bum once when I was implementing a date to day of
week routine in an embedded system using Zellers Congruence.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Is OTP unbreakable?/Station-Station
Date: 09 Jun 2000 07:55:34 EDT
Douglas A. Gwyn wrote:
>
>Tim Tyler wrote:
>> If the message were sandwiched at a genuinely random position within
>> 1K of random bytes before the OTP was applied (with some signal for
>> stripping the data off again), this attack would succeed only one
>> time in a thousand - rather than every single time.
>
>No, it would succeed every time, if the cryptanalyst were competent.
I believe that you are wrong. Cryptanalysis cannot derive a plaintext
from an OTP encrypted ciphertext, even assuming infinite resources.
The known plaintext/man in the middle/message substitution attack
does not rely on a particular clever attacker - it's a simple attack.
It does, however, require known plaintext. Put between 1 and 1000
(how many chosen at random) random characters at each end of the
plaintext before encrypting, and the known plaintext/man in the
middle/message substitution attack fails for lack of known plaintext.
(the random number of random characters at each end is superior to
Tim Tyler's method, because it forces the attacker to guess the length
of the plaintext as well as the position)
------------------------------
** 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
******************************
