Cryptography-Digest Digest #419, Volume #13 Thu, 4 Jan 01 11:13:00 EST
Contents:
Re: Very Simple Gift Certificate Scheme ("John A. Malley")
Re: SHA Padding (Stephan T. Lavavej)
Re: Intel holding back because of security issues! (Paul Rubin)
Re: nonstandard MD5 hash function... has anyone seen this? (Glide)
Re: A Censorship Resistant Digital Magazine Scheme (Ross Anderson)
Re: Differential Analysis (Ross Anderson)
NSA and Linux Security (David Bernier)
Re: Q: COFDM (John Sager)
Re: NSA and Linux Security (Stephan Eisvogel)
Re: Intel holding back because of security issues! (DJohn37050)
Re: Test values ("[Basic]")
Re: Birthday attack explanation... ([EMAIL PROTECTED])
Re: WinGPG 1.0 - A free, compact, non-ADK Windows alternative to PGP ("David
Thompson")
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Very Simple Gift Certificate Scheme
Date: Wed, 03 Jan 2001 22:22:33 -0800
Matthew Skala wrote:
>
> In article <[EMAIL PROTECTED]>,
> John A. Malley <[EMAIL PROTECTED]> wrote:
> >What does the hash help protect against if Alice, Bob and Carol pass the
> >certificates to one another via secure channels, only Alice knows the
> >complete set of serial numbers issued, and the serial numbers are
> >selected at random uniformly distributed across 0 - (2^k - 1)?
>
> I don't think the hash is necessary at all, although as Tom says in his
> followup, it may make it easier to issue the certificates if no good
> random number generator is available when the certificates are being
> issued (although in that case, where did the secure key from? why not use
> it as a PRNG seed?).
I reached the same conclusion after reviewing Tom's protocol, but
none-the-less asked the question o make sure I didn't miss some subtle
truth.
Hashing the (serial number | private key) concatenation as H = Hash( Sn
| Key ) and sending a certificate as < H, Sn > is not necessary,
either. Alice randomly selects an initial k-bit number S over the range
0 - (2^k - 1) with uniform probability. She uses this as a seed value
for a deterministic function f() that generates subsequent numbers over
the range 0 - 2^k -1 or some subset of that range. Alice hashes each
output of f, f(n), and provides the H'(n) = Hash( f(n) ) as the "random"
serial number that IDs a certificate. She keeps track of every H'(n) she
ever generates as the list of legitimate certificate numbers and the
current Sn[n] value to increment for the H'(n+1) value.
If Bob and Carol only ever see the hashed values, and the hash is
secure, then they cannot work out the incremental f(n) values feeding
into the hash function. They can only guess certificate values.
Alternatively Alice could use a CSPRBG to generate uniformly distributed
serial numbers on 0..2^k - 1, starting from a coin-flip generated seed
value.
>
> The Kosmos Online project discussed a similar concept under the heading of
> "issuing servers". There, we had a situation where players and
> subordinate servers in a role-playing game would be given "items"
> representing things in the game, and permitted to transfer them amongst
> each other but with a need for the transfers to be one-way: I can give you
> something but then once you have it I can't take it back. Also, we wanted
> to prevent things like double-spending. Some aspects of our situation were:
>
> * Items had to be testable for authenticity
> * Forging of items had to be impossible
> * Items had to be transferable
> * Little, if any, requirement for anonymity
> * All transactions could involve interactions among all the parties
> * Plenty of computer power available
> * The central server that gave out the items was trusted
>
> Our solution was simple: when the server creates an item, it gives it a
> random serial number. When I want to give you an item, you take it to the
> server and say, "Is this genuine?, and if so, give it a new serial
> number." The server, which knows about all the numbers it has issued,
> gives you a fresh number, transfers the value to that number, and marks
> the old one invalid. That way I can't take the item back unless you give
> me the new number. I can't forge an item because I can't guess the
> server's serial numbers. Interestingly, before cooking up the simple
> serial-number system we looked at a more elaborate system involving keyed
> hashes, quite similar to Tom's; we rejected that because it seemed to be
> simply unnecessary.
>
> This is discussed, buried among lots of interesting but non-cryptographic
> content, in the mailing list archive slice at
> http://www.islandnet.com/~mskala/kosmos1.txt
> Search on "issuing server" for messages about this topic.
Thanks for the URL and the info.
John A. Malley
[EMAIL PROTECTED]
> --
> Matthew Skala
> [EMAIL PROTECTED] :CVECAT DELENDA EST
> http://www.islandnet.com/~mskala/
------------------------------
From: stl/*This_is_a_comment*[EMAIL PROTECTED] (Stephan T. Lavavej)
Subject: Re: SHA Padding
Date: Thu, 04 Jan 2001 07:03:27 GMT
>I would say it implements SHA-1 padding faithfully for message length
>multiple of 8 bits.
Cool! :->
> Isolating the padding stuff in a single getpad()
>function certainly makes it easy to understand this logic.
It sucked considerably more in the beginning, believe me.
>The single non-conformance to ANSI C99 (ISO/IEC 9899:1999) that I
>spotted is the silent assumption fgetc() returns 8 bits at a
>time, when according to the standard it returns CHAR_BIT bits at a
>time, with CHAR_BIT>=8. Although it is pretty common that CHAR_BIT=8,
Indeed, I do make the silent assumption that characters are 8 bit
bytes. A small imperfection that I won't bother fixing. ;-)
-*---*-------
Stephan T. Lavavej
http://quote.cjb.net
stl/*This_is_a_comment*[EMAIL PROTECTED]
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Crossposted-To: comp.sys.laptops
Subject: Re: Intel holding back because of security issues!
Date: 03 Jan 2001 23:54:17 -0800
[EMAIL PROTECTED] writes:
> To make a long story short, I'm a senior in college and recently a
> sweet consulting job after graduation. My friend recently in the job
> hunting process went over to Sacramento to interview with Intel. Among
> things that he was told was this gem: "We can't release the Itanium (
> IA-64 ) processor because it can crack 128-bit SSL encryption in less
> than a day." LOL. If that's true, that's some sick CPU.
> -Boucher
Funniest thing I've heard all day... (crosspost for amusement of
sci.crypt).
------------------------------
From: [EMAIL PROTECTED] (Glide)
Subject: Re: nonstandard MD5 hash function... has anyone seen this?
Date: Thu, 04 Jan 2001 09:10:28 GMT
You are correct. It is definitely MD5. But they are taking the
output, which is 16 bytes of 8-bit binary output (128-bit) and usually
contains many non-printable characters - and they are using base-64
encoding to change the hash output to all-printable 7-bit characters.
When you reduce the bit count you "expand" the amount of characters in
the data, hence the more-than-16 characters in the output.
This is becoming a _very_ common practice in ecryption activeX
controls for web-based (asp, javascript, vbscript, etc), e-mail and
other applications that need to store and move things around as text,
as opposed to good-old binary.
On Wed, 03 Jan 2001 23:58:15 GMT, [EMAIL PROTECTED] wrote:
>I am trying to figure out how a particular hash function works. From clues
>in the documentation it appears to be some iteration of md5, but I haven't
>been able to figure out how it differs. The hashes look like the following:
>
>kS7IA7LOSeSlQQaNSVq1cA==
>
>is the hash for "asdf" (all lower-case). The function is case-sensitive and
>functions like any other hash function insomuch that a string of variable
>length always results in a 24 character hash. One unique feature of this
>function is the hashes contain characters other than letters and numbers.
>Another unique feature, and one which continues to puzzle me, is that all
>hashes end with "==", such as:
>
>the hash for "aaa" is R7zlx09Yn0hn29V+nKn4CA==
>the hash for "Aaa" is 5KzOFMS6+W/sMBfHQJUEzg==
>
>Any help on with this matter would be greatly appreciated. Thanks!
>
>-Mark-
>
>
>Sent via Deja.com
>http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (Ross Anderson)
Crossposted-To: alt.cypherpunks
Subject: Re: A Censorship Resistant Digital Magazine Scheme
Date: 4 Jan 2001 10:40:10 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (George Weinberg) writes:
>A Censorship Resistant Digital Magazine Scheme
> The situation I envision is something like, I've just written
>something
>I'll call "Rabid 0". My rabid fans are all eagerly awaiting Rabid 1,
>checking
>for it 4 times a day, but there are a bunch of posers who would like
>to put out their own magaizine called "Rabid 1" in hopes of stealing
>my
>audience, and the government of Turkey would like to censor me by
>posting an
>empty page labelled "Rabid 1"
This is something like the `Guy Fawkes Protocol' which we invented at
Cambridge on 4th November 1996, while discussing how a modern day Guy
Fawkes, about to blow up the Houses of Parliament, could arrange
publicity for his cause --- but without getting caught.
(For the benefit of readers unfamiliar with British history, Fawkes
conspired to blow up King James the first and the Houses of Parliament
in 1605; this was an attempt to end the persecution of Roman Catholics.
Fawkes was caught as a result of a comsec failure - a coded letter from
one of the conspirators was intercepted and deciphered. After his
public execution, Parliament ordained the 5th of November as a day of
thanksgiving for their narrow escape, and it is still celebrated by
bonfires and fireworks displays.)
The idea we came up with was that Fawkes would publish a hash of a
message, then blow up the Houses of Parliament, then publish the text
of the message which would say something like `We'll blow up Parliament
tomorrow and our demands will subsequently be authenticated with a
password whose hash is X'. By chaining successive hashes together, it
becomes possible to do digital signatures with only two hash function
computations per message, plus a reference toa timestamping service.
The eventual application of this technology was in signing digital data
streams, where you want to protect a whole stream of (say) video with
only one proper digital signature at the start of the film to bootstrap
things.
For more, see ``A New Family of Authentication Protocols'' on my home
page http://www.cl.cam.ac.uk/users/rja14/
Ross Anderson
------------------------------
From: [EMAIL PROTECTED] (Ross Anderson)
Subject: Re: Differential Analysis
Date: 4 Jan 2001 11:01:22 GMT
>In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>> Could anyone point me to an _online_ resource which describes exactly
>> how to do differential analysis?
In article <93006j$kpe$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> writes:
>
>Yeah, i'd like to see a consise description to. I wonder wether one of
>the experts would like to create such a document
I append the relevant page from my forthcoming book on security engineering
<http://www.cl.cam.ac.uk/~rja14/book.html>. If you want more detail (and
exercises to work on), I'd suggest Doug Stinson's textbook, which is at
<http://www.cacr.math.uwaterloo.ca/~dstinson/CTAP.html>, for differential
cryptanalysis (see chapter 3). I don't know of any good teaching material
on linear attacks, I'm afraid
Ross Anderson
*****
Choice of S-boxes
Studying bad choices of S-box gives us our entry into the theory of
block ciphers. Suppose for example that the S-box were the permutation
that maps the inputs (0,1,2,...,15) to the outputs
(5,7,0,2,4,3,1,6,8,10,15,12,9,11,14,13). Then the most significant
bit of the input would come through unchanged as the most significant
bit of the output. If the same S-box were used in both rounds in the
above cipher, then the most significant bit of the input would pass
through to become the most significant bit of the output. This would
usually be a bad thing; we certainly couldn't pretend that our cipher
was pseudorandom.
Linear Cryptanalysis
Attacks on real block ciphers are usually harder to spot than in this
artificial example, but they use the same ideas. It might turn out
that the S-box had the property that bit one of the input was equal to
bit two plus bit four of the output; more commonly, there will be
linear approximations to an S-box which hold with a certain
probability. {\em Linear cryptanalysis}~\cite{Matsui} proceeds by
collecting a number of relations such as `bit 2 plus bit 5 of the
input to the first S-box is equal to bit 1 plus bit eight of the
output, with probability 13/16' and then searching for ways to glue
them together into an algebraic relation between input bits, output
bits and key bits that holds with a probability different from one
half. If we can find a linear relationship that holds over the whole
cipher with probability $p = 0.5 + 1/M$, then according to probability
theory we can expect to start recovering keybits once we have about
$M^2$ known texts. If the best linear relationship has an $M^2$
greater than the total possible number of known texts (namely $2^n$
where the inputs and outputs are $n$ bits wide), then we consider the
cipher to be secure against linear cryptanalysis.
Differential Cryptanalysis}
{\em Differential Cryptanalysis}~\cite{BS} is similar but is based on
the probability that a given change in the input to an S-box will give
rise to a certain change in the output. Typically one finds that
tweaking some combination of input bits will cause some combination of
output bits to change with a probability slightly different from one
half. The analysis procedure is to look at all possible input
difference patterns and look for those values $\delta_i$, $\delta_o$
such that an input change of $\delta_i$ will produce an output change
of $\delta_o$ with particularly high (or low) probability. A typical
observation on an eight bit S-box might be that `if we flip input bits
2, 3 and 7 at once, then with probability 11/16 the only output bits
which will flip are 0 and 1'.
As in linear cryptanalysis, we then search for ways to join things up
so that an input difference, which we can feed into the cipher, will
produce a known output difference with a useful probability over a
number of rounds. Given enough chosen inputs, we will see the expected
output, and be able to make deductions about the key. As in linear
cryptanalysis, it's common to consider the cipher to be secure if the
number of texts required for an attack is greater than the total
possible number of different texts for that key. (One has to be
careful though of pathological cases, such as if you had a cipher with
a 32-bit block and a 128-bit key with a differential attack whose
success probability given a single pair was $2^{-40}$. Given a lot of
text under a number of keys, you'd eventually solve for the current
key.)
There are a quite a few variants on these two themes. For example,
instead of looking for high probability differences, we can look for
differences that can't happen (or that happen only rarely). This has
the charming name of {\em impossible cryptanalysis}, but it quite
definitely possible against many systems~\cite{BB99}. There are also
various specialised attacks on particular ciphers.
Cited references
\bibitem{BS}
E Biham, A Shamir, {\em `Differential Cryptanalysis of the Data Encryption
Standard'}, Springer (1993) ISBN 0-387-97930-1
\bibitem{BB99}
E Biham, A Biryukov, ``Cryptanalysis of Skipjack Reduced to 31 Rounds Using
Impossible Differentials'' in {\em Advances in Cryptology -- Eurocrypt 97},
Springer LNCS v 1592 pp 12--23
\bibitem{Matsui}
M Matsui, ``Linear Cryptanalysis Method for DES Cipher'', in {\em Advances in
Cryptology --- Eurocrypt 93}, Springer LNCS v 765 pp 386--397
------------------------------
From: David Bernier <[EMAIL PROTECTED]>
Subject: NSA and Linux Security
Date: Thu, 04 Jan 2001 11:58:57 GMT
NSA has recently announced that it is working on improving
the security of Linux...
reference: http://www.nsa.gov/selinux/index.html
David Bernier
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (John Sager)
Subject: Re: Q: COFDM
Date: 4 Jan 2001 14:32:59 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen <[EMAIL PROTECTED]>
writes:
:
: I came across the term COFDM, coded orthogonal frequency
: division multiplexing. Would someone please tell in what
: aspects it distinguishes itself from FDM and CDM? What are
: its specific advantages? Any literature pointers?
:
The European DVB-T transmission spec, which uses COFDM, is available from
www.etsi.org. Press the 'publications & products' button, then
'publication download area', then seach for '300 744' in category
'standard type & documentation no'. You can download a copy free if
you register with them.
--
John
--
Sorry about the address.
This is me, not BT.
------------------------------
From: Stephan Eisvogel <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Thu, 04 Jan 2001 15:34:04 +0100
David Bernier wrote:
> NSA has recently announced that it is working on improving
> the security of Linux...
Yes. Some observations:
1. "We give back to you guys" raised a lot of people's attitude over the NSA as
a whole, away from the big-bad-guys theme. In GPL you are what you give.
2. They had a newline buffer-overflow problem but there has already been a fix
announced at http://marc.theaimsgroup.com/?l=selinux&m=97847509307650&w=2
Of course this was found very early because the source code came from such
a promiment place.
3. While reading through http://www.nsa.gov/selinux/example_config.html I keep
thinking about NSA's real world structure (air-gaps, need-to-know, domains)
having been imported into the Linux kernel.
4. Selinux is the best attempt so far to rid Un*x-like systems from the big
drawback of having almighty powers as 'root'. There are other approaches
like LIDS, sudo or the evil suid-bits, but they all do not separate policy
from enforcement (i.e. once God, laws no longer apply to you). FreeBSD
tries to solve this on their own with the jail(2) system-call.
5. Building on 4., once this is stable and included in the main tree one
could envision a compromised system (e.g. through ftpd) that keeps running
in safety because security policies protect the remaining system from
tampering and snooping.
--
Stephan Eisvogel, Hartmannstrasse 129 App.119, 91058 Erlangen DE
mailto:[EMAIL PROTECTED] tel ++49 (0)9131 127876
HAWO-Network Administration & Security
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Date: 04 Jan 2001 15:23:24 GMT
Subject: Re: Intel holding back because of security issues!
I want one!!!
Don Johnson
------------------------------
From: "[Basic]" <[EMAIL PROTECTED]>
Subject: Re: Test values
Date: Thu, 4 Jan 2001 16:24:24 +0100
"Wei Dai" <[EMAIL PROTECTED]> schrieb im Newsbeitrag
news:[EMAIL PROTECTED]...
> In article <930b3o$v6s$03$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
> > I once again request test values for the gost 28147-89 algo. Could pls
> > anyone encrypt a sample block of plaintext in ecb mode and post the
> > plaintext, the ciphertext, the key and the sboxes here.
>
> From Crypto++:
>
> // these are the S-boxes given in Applied Cryptography 2nd Ed., p. 333
> const byte GOST::sBox[8][16]={
> {4, 10, 9, 2, 13, 8, 0, 14, 6, 11, 1, 12, 7, 15, 5, 3},
> {14, 11, 4, 12, 6, 13, 15, 10, 2, 3, 8, 1, 0, 7, 5, 9},
> {5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11},
> {7, 13, 10, 1, 0, 8, 9, 15, 14, 4, 6, 12, 11, 2, 5, 3},
> {6, 12, 7, 1, 5, 15, 13, 8, 4, 10, 9, 14, 0, 3, 11, 2},
> {4, 11, 10, 0, 7, 2, 1, 13, 3, 6, 8, 5, 9, 12, 15, 14},
> {13, 11, 4, 1, 3, 15, 5, 9, 0, 10, 14, 7, 6, 8, 2, 12},
> {1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12}};
>
> key plaintext ciphertext:
>
> BE5EC2006CFF9DCF52354959F1FF0CBFE95061B5A648C10387069C25997C0672
> 0DF82802B741A292 07F9027DF7F7DF89
>
> B385272AC8D72A5A8B344BC80363AC4D09BF58F41F540624CBCB8FDCF55307D7
> 1354EE9C0A11CD4C 4FB50536F960A7B1
>
> AEE02F609A35660E4097E546FD3026B032CD107C7D459977ADF489BEF2652262
> 6693D492C4B0CC39 670034AC0FA811B5
>
> 320E9D8422165D58911DFC7D8BBB1F81B0ECD924023BF94D9DF7DCF7801240E0
> 99E2D13080928D79 8118FF9D3B3CFE7D
>
> C9F703BBBFC63691BFA3B7B87EA8FD5E8E8EF384EF733F1A61AEF68C8FFA265F
> D1E787749C72814C A083826A790D3E0C
>
> 728FEE32F04B4C654AD7F607D71C660C2C2670D7C999713233149A1C0C17A1F0
> D4C05323A4F7A7B5 4D1F2E6B0D9DE2CE
>
> 35FC96402209500FCFDEF5352D1ABB038FE33FC0D9D58512E56370B22BAA133B
> 8742D9A05F6A3AF6 2F3BB84879D11E52
>
> D416F630BE65B7FE150656183370E07018234EE5DA3D89C4CE9152A03E5BFB77
> F86506DA04E41CB8 96F0A5C77A04F5CE
>
> --
> http://cryptopp.com - a free C++ class library of cryptographic schemes
thanks a lot. I tested three of the samples and I got the same results.
Although GOST has 32 rounds, I get a devision by zero when calculating the
cipher speed in bytes per millisecs.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Birthday attack explanation...
Date: Thu, 04 Jan 2001 15:44:30 GMT
> The point you missed is that 2^80 _is_ a large number.....
> Here it is in decimal: 1,208,925,819,614,629,174,706,176
>
> Now to quantify this large number, if two SHA-1 computations takes
0.01
> seconds then it would take 383,085,475,325,953 years to find a
> collision on average.
Yes, both of you are perfectly right, I hadn't realized. I was somehow
expecting 2^500, not realizing 2^80 was already so large...
Thanks very much.
Axelle.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "David Thompson" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: WinGPG 1.0 - A free, compact, non-ADK Windows alternative to PGP
Date: Thu, 04 Jan 2001 06:02:16 GMT
Ed Suominen <[EMAIL PROTECTED]> wrote :
...
> The source for the compression utilities used during encryption/decryption
> does not appear to be available but the those utilities are interchangeable
> with any open-source command-line ZIP utilities, if such exist. (Let me know
> of any, please!) All the actual encryption/decryption is done with
> open-source, GPL'd software. (I wouldn't have it any other way!)
>
Do you mean full ZIP including archiving, i.e.
saving and restoring file names and attributes;
or only the compression (now) used in ZIP,
and also in gzip, the LZ77 variant "deflate"?
If the latter, gzip is of course GNU/GPL,
and is largely based on the Info-Zip code
originally by Jean-Loup Gailly which is
open-source but not copyleft/GPL
and can be used as a callable library
as well as command-line programs
(available from www.info-zip.org ,
now hosted at www.freesoftware.com )
--
- David.Thompson 1 now at worldnet.att.net
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
