Cryptography-Digest Digest #156, Volume #11 Sat, 19 Feb 00 03:13:01 EST
Contents:
Re: NTRU Speed Claims (100x faster, etc.), explained (Dr. Yongge Wang)
Re: Keys & Passwords. ("r.e.s.")
Re: Keys & Passwords. (Bryan Olson)
In the diaries of Markku J. Saarelainen, the Caspian Oil is one of the ("William A.
Nelson")
Re: NSA Linux and the GPL ("Douglas A. Gwyn")
Re: NSA Linux and the GPL ("Douglas A. Gwyn")
Re: EOF in cipher??? ("Douglas A. Gwyn")
Re: EOF in cipher??? ("Douglas A. Gwyn")
Re: EOF in cipher??? ("Douglas A. Gwyn")
Re: EOF in cipher??? ("Douglas A. Gwyn")
Re: EOF in cipher??? ("Douglas A. Gwyn")
Re: EOF in cipher??? ("Douglas A. Gwyn")
Re: EOF in cipher??? ("Douglas A. Gwyn")
Re: EOF in cipher??? ("Douglas A. Gwyn")
Re: NSA Linux and the GPL (Dennis Ritchie)
Re: EOF in cipher??? ("Douglas A. Gwyn")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Dr. Yongge Wang)
Subject: Re: NTRU Speed Claims (100x faster, etc.), explained
Date: 19 Feb 2000 03:59:19 GMT
John Myre ([EMAIL PROTECTED]) wrote:
: Mike Rosing wrote:
: >
: > John Myre wrote:
: > > <snip>
: > > In their example parameter sets, we have:
: > >
: > > (expansion) plain cipher
: > > security N q p log(q)/log(p) bits bits
: > > ----------------------------------------------------
: > > moderate 107 64 3 3.8 170 642
: > > high 167 128 3 4.4 265 1169
: > > highest 503 256 3 5.0 797 4024
: > >
: > > (approximately)
: >
: > I think that's a bit too high. After asking Joe Silverman lots
: > of dumb questions, he explained that you can get it down to 3:4
: > plain:cipher ratio. Still, there's definitly expansion.
: Where does my reasoning fail?
I think the 3:4=plain:cipher is obtained by re-using some randomness
(I donot have the paper at hand and do not want to bother to check it,
but if you are really interested in it, you may find it in their
ANTS paper--can be downloaded from www.ntru.com)
Roughly I remember that after the first encryption,
the second message is encrypted with some info from the
first ciphertext...or...i forget the details and canot
get this 3:4 now
: I.e., is it true, or not true, that the plaintext is a set of N
: values modulo p? (If true, the plaintext has at most N * log(p)
: information in it).
: Is it true, or not true, that the ciphertext is a set of N values
: modulo q? (If true, the ciphertext takes N * log(q) bits to
: represent).
: Is N different between plaintext and ciphertext? Or the same?
: If the statements above are right, then the expansion is in
: fact log(q)/log(p). Did I do the arithmetic wrong?
: Did I use poor values for p and q? That is, maybe p can be a
: lot bigger (closer in size to q) and the system still works?
: (Maybe I even copied the numbers wrong from their web page?)
: John M.
--
======================================================.
Yongge Wang |
Center for Applied Cryptographic Research |
University of Waterloo |
Waterloo, Ontario, N2L 3G1 |
Canada |
Phone:(519)8884567 x 5295 |
[EMAIL PROTECTED] |
http://cacr.math.uwaterloo.ca/~ygwang |
======================================================'
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Keys & Passwords.
Date: Fri, 18 Feb 2000 20:11:44 -0800
"Trevor Jackson, III" <[EMAIL PROTECTED]> wrote ...
: Mok-Kong Shen wrote:
: > [EMAIL PROTECTED] wrote:
: > >
: > > This is a little off topic, but let's say I have a program that takes
a
: > > password and then converts that into a 256 byte array. That array is
in
: > > turn what's used to cipher the data.
: > >
: > > Does that mean the program is 2048bit encryption (256B = 2048b)? If
not
: > > what determines the bit level security (is it the original key or
what's
: > > actually used to cipher the data)?
: >
: > If your password has n bits then (assuming that these are random)
: > you can't get more than n bits of security out of that. It is
: > commonly assumed that the algorithm you use to generate sequences
: > is known to the opponent. The opponent simply needs to brute
: > force the n bits in the worst case. If the n bits are not (ideally)
: > random, then you have less security from the very beginning.
:
: I think the number of key bits is a red herring. The actual strength
(work
: factor) would be the binary logarithm of the number of possible encryption
: sequences for each message. Since this is often expressed in bits the
: confusion is natural.
:
: If the suggested 2048-bit key resulted in (say) 2^200 distinct cipher
texts
: per plain text (or vice versa) it would have a strength of 200 bits.
I trust that experts will correct if I err:
The first of the above replies concerns the "password space",
i.e. the set of possible passwords, while the other concerns the
"key space", i.e. the set of possible keys. It's the "effective"
size of the password- or key- *space* that's important here, not
the *storage* size of the password or key.
E.g. say a 20-character alphanumeric password is 160 bits long --
at best that's about a 103-bit password space, since there can only
be (26+10)^20 ~ 2^103 of such passwords; also, the "effective"
password space is much smaller than that if the pw is not random,
since in that case many passwords are very unlikely.
If such a password is then used, e.g., to generate 256 bytes of
key material to initialize ARC4's 256-byte state-vector, then the
password is the weak point on which a brute force attack would
focus. That's because ARC4's state-vector is managed internally as
a permutation of 256 distinct values, for a keyspace of size
265! ~ 2^1684. Note that, as with the pw, it's the key *space*
size of 1684 bits that matters, not the key *storage* size of
256*8=2048 bits. (It's possible that far from all of the different
keys produce distinct keystreams, but it's also possible that
practically all of them do -- I don't know if such details are
presently known about ARC4. Of course if enough is known about
the cycle properties, then this could become the focus of attack,
rather than the password or key.)
The above makes the assumption that an attacker knows the algorithm
itself, including how the key is generated from the password.
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Keys & Passwords.
Date: Sat, 19 Feb 2000 04:30:57 GMT
[EMAIL PROTECTED] wrote:
> This is a little off topic, but let's say I
> have a program that takes a password and then
> converts that into a 256 byte array. That
> array is in turn what's used to cipher the data.
>
> Does that mean the program is 2048bit encryption
> (256B = 2048b)? If not what determines the bit
> level security (is it the original key or what's
> actually used to cipher the data)?
I gather that what you mean by "bit level security" is
the same as the key space, measured in bits.
First the excruciating technical answer: It's determined
by the probabilities of the keys as:
Summation over all keys k:
- probability(k) * log_2(probability(k))
Some algorithms have "equivalent keys" and we should really
consider the distinct functions induced by the keys rather
than the keys themselves.
Informally you can think of the key entropy as the smallest
possible representation of the secret information. So if
you stretch a short password into a long array, it's still
at most the size of the password.
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "William A. Nelson" <[EMAIL PROTECTED]>
Crossposted-To:
alt.politics.org.cia,soc.culture.russian,soc.culture.soviet,soc.culture.europe,soc.culture.venezuelan,soc.culture.israel,alt.2600,soc.culture.nordic,soc.culture.china
Subject: In the diaries of Markku J. Saarelainen, the Caspian Oil is one of the
Date: Sat, 19 Feb 2000 05:18:49 GMT
When I stole the diaries of Markku J. Saarelainen, I knew that he had
some considerable knowledge of certain aspects of the Caspian Oil and
Caucasus. In his diaries, he wrote in April, 1999 that the main events
are going to happen in Caucasus and not in Yugoslavia. He seemed to have
understood the real reasons for the war in Balkans and the role of oil
in the world economy. This is amazing and at the same time interesting,
because I do not find any record at all that he ever studied any oil
related subject matters during his education in any universities. But he
did indeed seem to understand the world politics of oil business and
related industries.
Yours,
William A. Nelson
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA Linux and the GPL
Date: Sat, 19 Feb 2000 06:11:57 GMT
John Savard wrote:
> However, the NSA might have wanted the security part to be written
> from scratch, so that any known flaws in BSD would not be a problem.
Oh, good grief! NSA was one of the very first licensees of UNIX
source code, and has had various flavors of UNIX, among numerous
other OSes (including some devised within NSA), for decades. There
is no particular reason they need to use Linux as opposed to more
fully developed genuine UNIX-based systems. It may well be that
one or more individuals or groups within NSA have an interest in
some uses of Linux, but it's certainly not part of a massive
corporate strategy to adopt it for most computing.
As another poster hinted, no matter how much the security of Linux
is beefed up, it will not become Multi-Level Secure, and hence its
security will never be relied upon to act as a barrier between the
public and classified information. Classified information is
protected by not being kept in the same places that the public has
access to.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: NSA Linux and the GPL
Date: Sat, 19 Feb 2000 06:33:03 GMT
[EMAIL PROTECTED] wrote:
> 1. As far as I can tell, Linux is doing a much better job of being a
> viable desktop alternative. I don't see many desktop applications
> being ported to a xBSD.
There is source-code portability, and there is executable portability.
If the application is coded to *source-code* standards including POSIX
and X11, then nothing special needs to be done to "port" it to any
environment that supports those standards. Binary executable files,
however, depend on machine architecture, system call structure, file
system hierarchy, object file format, and many other details. There
is usually a platform-specific "ABI" to specify such details for each
platform, so for example all Intel x86 applications running on some
flavor of UNIX should conform to the ABI in order to work on all
platforms of that type. Last I heard, Linux did not support the x86
UNIX ABI. Some other UNIX variants for x86 now have Linux emulation
layers, so that binaries built for Linux stand a good chance of being
usable anyway. Such an approach for a non-x86 architecture would pay
a heavy performance penalty, which makes source-code portability more
attractive overall.
For example, I have Solaris 7 (also Plan 9 and Windows 98/NT) on my
home Pentium, also at work on SPARC processors, and other machines at
work have other versions of UNIX on MIPS processors. Most of the
software I develop has to work on DSPs and oddball microprocessors as
well as on that variety of host systems. It would be insane to think
of Linux as a particularly attractive target under the circumstances.
(Although, if the Linux developers do a good enough job of supporting
the source-code standards, it should be a breeze to use my software
on Linux too.)
> I personally have never used a xBSD, but from what I've read they
> are very mature and perform exceptionally well. I am planning on
> trying out at least one of them sometime in the future mainly
> because I heard that they have excellent TCP/IP stacks.
Nearly everybody uses BSD-based implementations of the IP protocol
suite. (Unfortunately, these have had many security problems, but
that is another issue.) Even Microsoft "WinSock" is modeled after
the BSD interface. BSD UNIX itself is no longer under active
development.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Sat, 19 Feb 2000 06:49:12 GMT
Mok-Kong Shen wrote:
> To be sure that I didn't misunderstand, I like to ask whether the
> code (from KR):
> while ((C = getc(fp)) != EOF)
> .........
> needs to be modified or using rb is sufficient for taking care of
> the presence of any bit combinations in the file. Thanks.
You left out the important part, which is that the variable "C"
(you really should use lower-case!) has to be properly declared
as type int. If so, no data value returned by getc will match EOF;
only an actual end-of-file will cause getc to return EOF. The
meaning of "actual end-of-file" depends on whether the stream was
opened as a text stream or as a binary stream; if a text stream,
then on some systems an embedded special byte value, typically 1Ah,
will be interpreted as marking the end of the file, whereas if it
is a binary stream, only running completely out of data constitutes
end-of-file. (Subtle details ignored.) And as I already said,
other mappings such as converting 0Dh,0Ah pairs to '\n' is done
only for text streams; binary stream data is returned from getc
unmolested.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Sat, 19 Feb 2000 06:50:24 GMT
Johnny Bravo wrote:
> Unsigned char works if your compiler can handle it, ANSI C.
No, because then EOF will not be properly detected:
((unsigned char)EOF) != EOF.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Sat, 19 Feb 2000 06:52:57 GMT
Runu Knips wrote:
> Unfortunately, the above code will run on many systems without
> problems until fp is a binary file which happends to contain
> the code 0xff, which is equal to (signed char)-1 (on machines
> with 8 bits for a character).
Wrong again! When getc reads an FFh byte, it returns the
*int* value 0xFF, which is *never* equal to EOF.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Sat, 19 Feb 2000 06:54:07 GMT
John Myre wrote:
> (I suppose the whole thing would fail if "int" were 8 bits,
> but please - has there *ever* been such an implementation?)
The only interesting implementations are the ones that conform
to language standards. The C standard requires in effect that
int have at least 16 significant bits.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Sat, 19 Feb 2000 07:31:16 GMT
Mok-Kong Shen wrote:
> ... Could some experts please post a piece of C or C++ code
> for writing AND reading binary stuffs ...
If you can't sort out the correct responses, how are you going to
sort out the correct code postings? In fact, I posted correct
information on this. I'm not going to list all my C credentials
here, but for example I'm acknowledged in K&R 2nd ed. and am on
the C standards committee, which should be some indication.
/* copyfile -- make an exact copy of a file */
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
register int c;
register FILE *ifp, *ofp;
if (argc != 3) {
fprintf(stderr, "Usage: copyfile from to\n");
return EXIT_FAILURE;
}
if ((ifp = fopen(argv[1], "rb")) == NULL) {
fprintf(stderr, "copyfile: can't open %s\n",
argv[1]);
return EXIT_FAILURE;
}
if ((ifp = fopen(argv[2], "wb")) == NULL) {
fprintf(stderr, "copyfile: can't create %s\n",
argv[2]);
return EXIT_FAILURE;
}
while ((c = getc(ifp)) != EOF)
if (putc(c, ofp) != c) {
fprintf(stderr,
"copyfile: error writing %s\n",
argv[2]);
return EXIT_FAILURE;
}
if (ferror(ifp)) {
fprintf(stderr, "copyfile: error reading %s\n",
argv[1]);
return EXIT_FAILURE;
}
return EXIT_SUCCESS;
}
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Sat, 19 Feb 2000 07:37:15 GMT
Jerry Coffin wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> > But a strict reading of 7.9.7 indicates that the following is valid:
> > int c;
> > while ( (c=getchar() ) < 0 )
> > putchar( /* something about c */ );
> Well, no, I don't think so. I think you intended that to be a ">"
> instead of a "<" in the comparison. Once this is corrected, even the
> most casual reading makes it _extremely_ obvious that the code is
> correct.
Actually, it's still wrong, because it terminates the loop
upon reading a 0-valued byte.
Another problem is that getchar reads from stdin, which is a
text stream, not a binary stream. (Similarly for putchar.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Sat, 19 Feb 2000 07:46:43 GMT
"Trevor Jackson, III" wrote:
> You are out of line again. The original statement was that "all
> characters are returned as nonnegative values". That statement was
> false.
No, getc and getchar return nonnegative values for all input bytes
even when the implementation has chosen to make char a signed type.
> And there are machines where EOf != -1 and some where sizeof(char) ==
> sizeof(int). I've worked on them.
EOF doesn't have to be -1 but it *does* have to be a negative
integer constant, per the language standard. I know of no C
implementation that conforms to the language standard for which
sizeof(char)==sizeof(int). Indeed, it is almost unheard of for
CHAR_BIT to be other than 8 (or rarely these days, 9), because
of the prevalence of octet-based file storage and memory addressing.
The C standard requires int to have at least 16 bits. I would be
*very* interested in hearing of any conforming implementation of C
for which sizeof(int)==1.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Sat, 19 Feb 2000 07:53:42 GMT
Runu Knips wrote:
> ... A character value, however, is
> the smallest type which has at least 7 bit.
No, there have to be at least 8 bits in a char.
Char is the smallest unit of addressable storage at the
level of C source code, but the implementation can make it
larger than logically necessary so long as all requirements
are met. Because there has been no standard way to designate
an object type smaller than char in C, char is almost always
8 bits (unless the architecture is one of the antique ones
that has a non-power-of-two word size) in order to support
many C programmer's expectations that they will be able to
pick off octets by aliasing objects to arrays of char.
In principle, a conforming C implementation could make
char have 16 bits, but I am unaware of any that have done so.
------------------------------
From: Dennis Ritchie <[EMAIL PROTECTED]>
Subject: Re: NSA Linux and the GPL
Date: Sat, 19 Feb 2000 08:05:38 +0000
"Douglas A. Gwyn" wrote:
>
> John Savard wrote:
> > However, the NSA might have wanted the security part to be written
> > from scratch, so that any known flaws in BSD would not be a problem.
>
> Oh, good grief! NSA was one of the very first licensees of UNIX
> source code, and has had various flavors of UNIX, among numerous
> other OSes (including some devised within NSA), for decades....
Yes, indeed. An early visit to Ft. Meade provided some memorable experiences.
I shoulder-surfed the root password for a bunch of PDP-11/70 machines
("lettucein"). They weren't connected to the outside, of course.
I also learned that it can be harder to get data in than out. Carrying
in a tape with some Unix release required someone with a temporary
magic badge carrying big juju. Taking out a bunch of listings was less
trouble.
Dennis
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Date: Sat, 19 Feb 2000 08:08:03 GMT
"Trevor Jackson, III" wrote:
> However, for production code one cannot rely upon this. It leads to
> the mistaken assumption that...
> while ( ( c = getchar() ) > 0 )
> ... will work. On some compilers this will fail because they do not
> conform to the standard. I know of two.
That code is wrong anyway, as noted in another recent posting.
However, if a C implementation can't meet even such a simple
requirement as that of the values returned by getchar, why would
you use it at all? This isn't the sort of problem that is
worth guarding against, because there are an infinite number
of ways in which implementations could fail to meet clear specs.
In fact, I've never encountered this particular error in any
serious C implementation, and I've compiled C applications for
decades on dozens of platforms. (I *have* seen errors in this
area in *application source code*.) It should be obvious that
such an implementation error would turn up nearly immediately,
since it would break the well-known idiom for copying files.
------------------------------
** 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
******************************
