Cryptography-Digest Digest #825, Volume #8 Sat, 2 Jan 99 15:13:04 EST
Contents:
Help needed on simple cypher ("Keith")
Re: Birthday Attack calculations. (David Broughton)
Re: FAQ: as up to date as it should be? (R. Knauer)
Q: Key length: how is optimal length determined? (Roy G. Biv)
Re: Why no Standard C/R Password Protocol? (David P Jablon)
Re: Compound Cipher... (Rebus777)
Re: GSM Hack [Was Security through obscurity in the smartcard world] (frasta)
Off Topic (rosi)
DES programming (Henrik =?iso-8859-1?Q?B=E4=E4rnhielm?=)
Re: Birthday Attack calculations. (Peter Pearson)
Re: DES programming (Ladislav Sedivy)
Re: Transforming DES into a non-Feistel cipher (Jean-Jacques Quisquater)
Re: DES programming (Jari Arkko)
Re: Help needed on simple cypher ("Keith")
Re: PGP Keys on Smartcard (ibata)
----------------------------------------------------------------------------
From: "Keith" <[EMAIL PROTECTED]>
Subject: Help needed on simple cypher
Date: Sat, 2 Jan 1999 14:21:21 -0000
Here is a cypher from a Christmas quiz. I�m not a cryptographer, and could
use some help! I�ve tried using what I think is Playfair, with keys such as
Monsieur, Monseig(n)(e)ur, siez(i)(e)m(e), siez(i)(e)m(e)(s)(i)(e)cl(e)
without any joy. I�ve tried basic substitution, from an ABC� 5x5 table
against one offset by the keyword, and also using opposing diagonal
character substitution for letter pairs (gleaned from a Dorothy Sayers
book - Have his Carcase!)
�This year's cipher owes much to M. Mot-cl� de Tableau, a sixteenth-century
French cryptographer: GPAZF SUTBZ ARHRL IVXJO IVYWP QGZWE UUOGL SBWLX WSQWE�
All assistance greatly appreciated! This should be a cinch for you guys!
Thanks, Keith
------------------------------
From: David Broughton <[EMAIL PROTECTED]>
Subject: Re: Birthday Attack calculations.
Date: Sat, 2 Jan 1999 14:41:56 +0000
In article <[EMAIL PROTECTED]>, Fred Van Andel
<[EMAIL PROTECTED]> writes
> How does one calculate the exact number of documents that need to
> be hashed to ensure a collision? I know that it is approximately
> 1.2*2^(M/2), but what is the exact formula or procedure for
> calculating the number?
Try this formula:
w = n^g + 0.29 - e
where:
w = the number of documents to get 50% probability of a collision
n = number of different hash codes, all equiprobable
g = 0.5 + 1/(6.13 * ln(n))
ln() is the natural logarithm function
e is a small error that can be ignored in practice, usually < +- 1.
This is an empirical formula that I worked out many years ago and
filed away in a notebook.
The exact formula is the value of w in this equation:
( product from k = 1 to k = w-1 of (n-k)/n ) = 0.5
but this is not a practical calculation for large n.
As you can see, w is a bit larger than the square root of n. For
n = 10^6, for example, w = 1177.68 (e = -0.197).
If your formula is meant to be 1.2 * n^0.5, then w = 1200 for n =
10^6 which is getting there.
--
David Broughton
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: FAQ: as up to date as it should be?
Date: Sat, 02 Jan 1999 15:08:13 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 01 Jan 1999 22:04:29 GMT, [EMAIL PROTECTED]
(George Barwood) wrote:
>>Where is there a good FAQ on ECC?
>Try http://ds.dial.pipex.com/george.barwood/ec_faq.htm
Thanks,
Bob Knauer
"Who can protest an injustice but does not is an accomplice in the act."
--The Talmud
------------------------------
From: [EMAIL PROTECTED] (Roy G. Biv)
Subject: Q: Key length: how is optimal length determined?
Date: Sat, 02 Jan 1999 14:53:16 GMT
Or, in general, with a program like PGP why doesn't encryption
strength increase linearly with respect to keylength?
------------------------------
From: [EMAIL PROTECTED] (David P Jablon)
Subject: Re: Why no Standard C/R Password Protocol?
Date: Sat, 2 Jan 1999 15:57:01 GMT
John Savard wrote:
> Since hash functions aren't export controlled, why isn't there a nice,
> simple, non-proprietary standard for entering passwords over the
> Internet that doesn't require sending passwords in the clear?
I agree with one of your conclusions, that no technically-
adequate methods are based on hash functions alone.
Methods like EKE, SPEKE, and SRP use modular exponentiation
to prevent network brute-force attacks, and can also
prevent simple mis-use of a stolen verifier.
But the question and subsequent discussion seemed to be
based on some wrong assumptions:
1) That hash functions guarantee exportability.
They don't. Some exponentiation-based methods are
exportable, and some uses of hash functions are not.
2) That hash functions are simple.
Have you really looked closely at MD5 or SHA1? :-)
Can you fully describe them in a couple of sentences?
On the other hand, any high school student know should know
what modular arithmetic is. As for implementations, with
free source code in both categories, everything is simple.
3) That proprietary designs are a "bad thing".
Though this enters an arena of purely personal opinion,
I see patents as a driving force behind many advances
in technology, public-key crypto being just one example.
Sure, some people might only use a bargain-basement solution.
But I prefer to shop around, at least to see what's available.
Bryan Olson wrote:
> Actually there are a few [existing standards], they're just
> not widely implemented.
As one example, Bryan described a one-time-password system.
OTP's are an incomplete solution to the problem, with the
benefit that they can be used with old client software
designed only to permit clear-text passwords.
But if you have control of the client software,
you can do much better.
Eric Backus wrote:
> I recently discovered <http://srp.standford.edu/srp>, which may be
> exactly what you're looking for (and more?).
Better still, SRP is just one flavor of a whole generation
of methods designed specifically as an optimal solution to
this problem. For references to B-SPEKE, A-EKE, and others,
look at: <http://world.std.com/~dpj/links.html>
======================================================
David P. Jablon
Integrity Sciences, Inc.
[EMAIL PROTECTED]
<http://world.std.com/~dpj/>
------------------------------
From: [EMAIL PROTECTED] (Rebus777)
Subject: Re: Compound Cipher...
Date: 2 Jan 1999 17:02:31 GMT
But what about the block overlap, has this been looked into?
Are you saying it would be better to combine a stream cipher and a block
cipher, rather than 2 block ciphers?
[EMAIL PROTECTED] (Rebus777) wrote:
>> I got to thinking about what you
>> might have, if you combine 2 of the Tiny algorythms into one package.
>> Maybe Goldfish and TinyRC6.
>>
>> I was wondering if it Would be possible, or desireable, to offset the
>> second encryption by 2 or 3 bytes so that blocks from the second
>> encryption overlaped the blocks from the first encryption? If
>> speed became a factor, maybe some rounds could be cut back in the
>> individual algos. I think only one password entry would be good also.
>>
>> Does this seem like something that would be of benefit?
>> I have heard of the possible weekness introduced when 2 block ciphers
>> are combined, but I thought that the offset I have proposed might
>> over come this and produce a strong encipherment.
>>
[EMAIL PROTECTED] (wtshaw) Replied:
>Rules of thumb when chaining algorithms: they should have as little in
>common as possible; it might make a difference which is used first; the
>ciphertext from the first encryption should not be easily recognized so as
>to inhibit or prevent staged solutions; rules of thumb may or may not
>apply, or be understatements, so be careful.
>
>Consider an ancient category, tableau ciphers, and consider a more recent
>one, a simple block cipher, and, having done a pair of implementations
>partly for the chance to use one key structure, in two wildly different
>algorithms, the result can produce something much stronger through
>chaining than with either alone. If I followed, the rules for chaining,
>it becomes rather a pain to think about solving them both together.
>
>this is the input text used for the message and to generate the keys used
>in both algorithms.
>
>The two algorithms are Code Blue and Trinity 27, but encryption must be
>first in Trinity 27, or there is a conflict in formats. Here are the
>keys, identical:
>
>Subs1(T27): sfipjqtgb klnyuvc/w zrdaemoxh
>Subs2(T27): eqfvwamgb rdxtnhsiu cyjzokpl/
>Trans(T27): s/tdciobp xfameqrjy gnuzhkvlw
>
>Key1(CB): sfipjqtgb klnyuvc/w zrdaemoxh
>Key2(CB): eqfvwamgb rdxtnhsiu cyjzokpl/
>Key3(CB): s/tdciobp xfameqrjy gnuzhkvlw
>
>In Trinity 27, text is preformatted and last group is padded to 9 characters:
>this/is/t he/input/ text/used /for/the/ message/a nd/to/gen erate/the
>/keys/use d/in/both /algorith msxelgxof
>
>Ciphertext from Trinity 27 and Plaintext for Code Blue:
>fpbarzeek lcixnsltf g/wtxnepu smokuvhhb qzlozelcn m/azldiss vkgl/wzzi
>vdryadnox jsljszplc d/mfyxhpx sqpcutlai
>
>Ciphertext from Code Blue:
>mxgbkyzch zqjrshlbv bmacfxbuo ekxejbprs viyzdjwwi rfxsunqln rvtjfjvnl
>tuttqt/ec rytvpstsf cnecireml bcqkiqlmc
>
>Regrouped and padded an extra character to hide the 9 character groups:
>mxgbk yzchz qjrsh lbvbm acfxb uoekx ejbpr sviyz djwwi rfxsu nqlnr vtjfj
>vnltu ttqt/ ecryt vpsts fcnec ireml bcqki qlmcr
>
>Aside from the weird slant sign in one group, which might be taken as an
>indicator of some kind, a analysis type guy or gal has a real problem
>knowing where to start to wrestle with it. Keep all your messages short
>and chain the keys, to protect the comments about where you store you
>jelly bellies.
>
>This paragraph for fellow keylength freaks: One could use two different
>sets of keys, each of the six keys having a keyspace of 27!, for a
>combined total keylength equivalent to 353.12 bits. Now, alone, Code Blue
>is a pretty weak sister, while Trinity 27 is a bit more formidable;
>together, chained just this way, we have a new algorithm, not much of a
>slacker come to think of it. Strangely enough, Trinity 27 is a lot faster
>cipher than Code Blue.
>
>Of course, these are limited ciphers, just done for such an example needed
>to illustrate my couple of points worth a penny a piece, or 0.16 Texas
>bits total, if you know the value of a bit a hundred years ago. The same
>concepts should not be lost in any other situation, no headers, no hitch'n
>posts midstream, ciphertext flowing from one algorithm to the next.
>
>Look closely at the two algorithms you want to chain together and see if
>they can follow the rules I gave.
------------------------------
From: frasta <[EMAIL PROTECTED]>
Subject: Re: GSM Hack [Was Security through obscurity in the smartcard world]
Date: Sat, 02 Jan 1999 18:33:46 +0100
Reply-To: [EMAIL PROTECTED]
Gurripato (x=nospam) wrote:
> On Thu, 31 Dec 1998 15:55:14 GMT, [EMAIL PROTECTED] (Gary Howland) wrote:
> >
> >One claim I have heard is that a SIM can be stolen, and copied onto
> >thousands of cards. Fine, we now have a problem. So what are the
> >service providers going to do? They'll just disable all *phones* that
> >use the stolen SIM.
>
> And see your business plummet down as soon as the general public
> discovers that a) your system is susceptible to cloning and b) that if
> it does, all the service provider can do is shut all clones down,
> including the legal one.
>
> >Once this happens, and it becomes public
> >knowledge that the use of a stolen SIM can effectively break your
> >mobile phone, then the market for these dodgy black market cards will
> >disappear, and so will the security problem.
>
> Not if the phone is stolen, the SIM copied (or even cloned) and
> given back to the owner, perhaps without he/she knowing it. Or if new
> techniques allow for the cloning witohut physical possesion of the SIM
> card (via multiple queries, for example).
You have *totally* missed Gary's point. There is a unique identifier in the PHONE as
well as on the SIM. People will not insert unknown SIMs into their phones for fear
of breaking them. This means there will be no *large scale* fraud.
> It is like saying: well, as soon as your Visa is stolen, you
> report it and it will be cancelled, therefore the burglars will gain
> nothing. And yet, Visas (and other credit cards) are stolen every day.
And even this system, with bugger all security, lives on, albeit with .5% of fraud
(or whatever the current rate is) GSM will do the same at a fraud rate of *much*
less.
>
> >However, if SIMs could be created from the data snatched from the
> >airwaves, rather than being stolen from hire cars etc., then, yes, we
> >have a serious security problem with the system. But this is not the
> >case, and there are currently no security concerns in this area.
>
> According to the Smartcard Developers Association, "no practical
> over-the-air attack is known yet but that should be not ruled out" (from
> an April 1998 press release, available at
> http://www.scard.org/press/19980413-01/) If "concerns" means to you
> "let�s not worry until it really happens" fine, but otherwise I think it
> is just a matter of time.
Complete and utter FUD.
> >Some people might claim that these extra security features should
> >already be in place - but why should a company waste time and money on
> >fixing something that is not yet a problem (as long as it knows it can
> >do so in the future)?
>
> For the same reasons our cars carry a spare tire even when
> travelling on good roads: no trouble ahead, but let�s be prepared in
> case there is any.
Gary's point is that the service providers *are* prepared, by having the
appropriate security features in the protocol - but it is just not worth the expense
of implementing some of them until necessary. (Using your analogy - sure, carry the
spare, but don't put it on until needed ...)
Francis.
------------------------------
From: rosi <[EMAIL PROTECTED]>
Subject: Off Topic
Date: Sat, 02 Jan 1999 06:43:47 -0800
R. Knauer wrote:
>
> "Who can protest an injustice but does not is an accomplice in the act."
> --The Talmud
(Like your quote, Bob)
(But never seriously)
"Who can expose a falsehood but does not is an accomplice in the lie."
--- (My Signature)
------------------------------
From: Henrik =?iso-8859-1?Q?B=E4=E4rnhielm?= <[EMAIL PROTECTED]>
Subject: DES programming
Date: Sat, 02 Jan 1999 18:41:11 +0100
I have thought about coding my own DES implementation, but I quickly got
the problem of how to represent 64-bit integers. I am using C, and maybe
C++. Is there a common way to do this? What have other people done?
Thanks
--
*****************
Henrik B��rnhielm
[EMAIL PROTECTED]
*****************
------------------------------
From: [EMAIL PROTECTED] (Peter Pearson)
Subject: Re: Birthday Attack calculations.
Date: Sat, 2 Jan 1999 19:11:25 GMT
In article <$[EMAIL PROTECTED]>,
David Broughton <[EMAIL PROTECTED]> wrote:
>In article <[EMAIL PROTECTED]>, Fred Van Andel
><[EMAIL PROTECTED]> writes
>
>> How does one calculate the exact number of documents that need to
>> be hashed to ensure a collision? I know that it is approximately
>> 1.2*2^(M/2), but what is the exact formula or procedure for
>> calculating the number?
>
> [snip]
>
>The exact formula is the value of w in this equation:
>
> ( product from k = 1 to k = w-1 of (n-k)/n ) = 0.5
>
>but this is not a practical calculation for large n.
To derive your own approximation formula from the above, exact
formula, rewrite it as follows:
n (n-1) (n-2) ... (n+1-w) n!
product = -------------------------- = ----------
n^w (n-w)! n^w
Then, use Stirling's approximation to make the factorials more
manageable. Stirling's approximation (see, for example, Knuth,
Art of Computer Programming, Volume 1) is:
ln( n! ) = (n+1/2) ln(n) - n + ln( 2*pi )/2 + 1/(12*n) - ...
You'll have to experiment with the number of terms required to
get meaningful results. Overimplifying to n*ln(n)-n gives conspicuously
nonsensical results. If memory serves, (n+1/2) ln(n) - n + ln( 2*pi )/2
is a good level of approximation, and one needs the approximation
ln(1+x) = x (for small x) as well.
- Peter
------------------------------
From: Ladislav Sedivy <[EMAIL PROTECTED]>
Subject: Re: DES programming
Date: Sat, 02 Jan 1999 14:16:26 -0500
Henrik B��rnhielm wrote:
>
> I have thought about coding my own DES implementation, but I quickly got
> the problem of how to represent 64-bit integers. I am using C, and maybe
> C++. Is there a common way to do this? What have other people done?
>
> Thanks
>
> --
> *****************
> Henrik B��rnhielm
> [EMAIL PROTECTED]
> *****************
Microsoft's VC++ has __int64 data type.
--
Lac
------------------------------
From: Jean-Jacques Quisquater <[EMAIL PROTECTED]>
Subject: Re: Transforming DES into a non-Feistel cipher
Date: Sat, 02 Jan 1999 20:28:35 +0100
This transformation was described in the paper of CRYPTO 83 (pp.
172-202) by M. Davio, Y. Desmedt, ..., Jean-Jacques Quisquater, ...:
see figures 8 and 9. This transformation helps to understand the weak
keys (found by Donald Davies) and accelerates some implementations
based on 48 bits (Burroughs computers: who knows today?).
Not useful for cryptanalysis. By the way, such ciphers were called
mixing transformations by Claude Shannon (1949).
Happy New Year!
Jean-Jacques Quisquater,
------------------------------
From: [EMAIL PROTECTED] (Jari Arkko)
Subject: Re: DES programming
Date: 2 Jan 1999 18:02:08 GMT
Reply-To: [EMAIL PROTECTED]
Henrik =?iso-8859-1?Q?B=E4=E4rnhielm?= writes:
>I have thought about coding my own DES implementation, but I quickly got
>the problem of how to represent 64-bit integers. I am using C, and maybe
>C++. Is there a common way to do this? What have other people done?
In C, most algorithms are coded with
unsigned long hi;
unsigned long lo;
On some architectures "long long" is also an option.
In C++, I suggest defining an abstract and a concrete class, and using
virtual functions to read and set bits :-)
Seriously though, writing your own algorithm implementation is a demanding
task and requires a thorough understanding of the implications of the
data structure selections. I've never written a DES implementation but I
understand it is far from trivial to make it efficient, given it's strange
design. It could require playing some tricks with even the data structures
used for representing the text to be encrypted. Just wanted to make sure
you knew where you were getting into... Look at Schneier's book for an
example DES implementation.
Jari
------------------------------
From: "Keith" <[EMAIL PROTECTED]>
Subject: Re: Help needed on simple cypher
Date: Sat, 2 Jan 1999 19:52:48 -0000
Sorted - Vigenere, and Monsieur was NOT the keyword.
------------------------------
From: ibata <[EMAIL PROTECTED]>
Subject: Re: PGP Keys on Smartcard
Date: Sat, 02 Jan 1999 12:01:51 -0800
Try http://www.incrypt.com/dlock01.html
I have not used these products, but stumbled across this wedsite by
accident. On another note, I'll be curious to know if anybody has used
this companies' products, esp. Invincible Disk. Is it as good as the
company claims it to be? I'll post a separate message and ask the
group.
fred wrote:
> Hi there.
>
> I'm a PGP User on Windows NT and would prefer to
> keep my secret keys on a smartcard which would always
> physically reside with me.
>
> Does such a product exist? I would ideally like to think that
> my secret keys always remained on the card and that signing
> and digest creationn occured on the card. That way my keys
> couldn't be snaffled away by a miscreant program on my NT
> workstation.
>
> Has anyone done this or am I about to make my fortune?
>
> Thanks in advance,
> Gavin
------------------------------
** 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
******************************
