Cryptography-Digest Digest #287, Volume #14 Thu, 3 May 01 13:13:01 EDT
Contents:
open source highscore server: impossible? (Marc Mutz)
Re: research on polymorphic crypto/Best Possible Privacy? (SCOTT19U.ZIP_GUY)
Re: new encryption idea (Roger Fleming)
Re: Message mapping in EC. (Nobody)
Re: Message mapping in EC. (Jean-Luc Cooke)
Re: DES sample vector (Rick Wash)
Re: A Question Regarding Backdoors (Rick Wash)
Re: Avoiding bogus encryption products: Snake Oil FAQ ("Simon Hunt")
RE: open source highscore server: impossible? (Gary)
Re: open source highscore server: impossible? (Sergei Lewis)
Re: Reusing A One Time Pad (Tim Tyler)
Re: DSA in GF(2^W)? ("Roger Schlafly")
Re: open source highscore server: impossible? (John Savard)
SAC2001 Final Call for Papers (Amr Youssef)
----------------------------------------------------------------------------
From: Marc Mutz <[EMAIL PROTECTED]>
Subject: open source highscore server: impossible?
Date: Thu, 3 May 2001 15:15:32 +0200
Hi!
On the KDE (Unix Desktop) games development list, we are currently
thinking about ways to provide
a.) a per-machine highscores
b.) (internet) highscore servers
as opposed to per-user highscore lists. The problem is that most
solutions that pop into the mind of the unwary allow easy cheating.
While we think that - roughly - providing each game with a certificate
at install time to authenticate against a setgid 'games' program and
making the involved binaries executable, but not readable, thus
preventing ptrace'ing of and poking-around in the binary, is enough to
prevent cheating of every local user (except root, of course), this
seems to not work for an internet highscore server that will collect
highscores from users all over the world.
The main problem seems to be that both the games and the highscore
server are to be open source.
Has anyone here an idea?
Thanks,
Marc
PS: http://lists.kde.org/?l=kde-games-devel&m=98884330006288&w=2
has the current proposal.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: research on polymorphic crypto/Best Possible Privacy?
Date: 3 May 2001 13:21:00 GMT
[EMAIL PROTECTED] (Mark Wooding) wrote in <[EMAIL PROTECTED]>:
>www.identification.de/crypto/descript.html
I was hoping that it would be good. Such a nice set of
graphics. But it appears to be more than wrong. Looking
at the graphs. One could pretend at the point of the XOR
that you have a OTP stream ( I am being nice ). Unfortunuatly
if one uses the same Key for two messages a "plain text attacl"
immediately breaks the methods. Since two messages encrypt
with same OTP gives one access to the XOR stream that was
used. You don't care what the Key was since the key not needed.
I won't give my usual rant about the NSA trying to trick someone.
This is so obviouly weak that I would be embarassed if they
thought the public was that dumb. However beautiful graphics
I wish I could design a webpage that nice.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (Roger Fleming)
Subject: Re: new encryption idea
Date: Thu, 03 May 2001 11:38:36 GMT
"G. Orme" <[EMAIL PROTECTED]> wrote:
> This is just an idea that will probably be flawed at this stage, but it
>seems like a different approach. The idea is that one must guess an
>encrypting algorithm instead of a password.
Umm, actually people have suggested that, and it has been generally regarded
as too inconvenient for practical use, and too difficult to analyse the
security. There are some who support the idea, umm, possibly Terry Ritter?
> Here is a basic example. Say you are encrypting some text. Letters are
>denoted as numbers a=1 to z=26, or some other combination. One has an
>equation which on inputting the letter's number (e.g. c=3) outputs a number
>which is the encryption of the letter, called here the output (this number
>would be very large). As an illustration say the minimum difference between
Up to the very large, so far this was a pretty general definition of ANY
character oriented cipher. The "very large" means there will necessarily be
data expansion, ie the ciphertext will be much longer than the plaintext. In
some situations this may not matter too much, but in many electronic
applications it is unacceptable.
>any output is a billion or more. That is, no encrypted number representing a
>letter is closer than a billion to any other. As an additional enhancement
>one could have it so the algorithm changes sequentially after encrypting
>each letter in a preagreed way so that for example all the "e"'s wouldn't be
>the same number. For example one algorithm encrypts the first letter,
>another encrypts the second letter, and so on. The algorithm could change in
>a way that is itself algorithm based. Instead of sending a new password one
>would send a new algorithm.
This algorithm changing is very complicated and inefficient (of time and
memory) to arrange in practice, unless the "new" algorithm can be specified by
a simple parameter. That, of course, is esentially what a key does.
> There would also be an additional input of for example random numbers
>which can alter the encrypted output number by say plus or minus a million.
[...]
Well, the example as stated is a bit vague. I can think of a totally insecure
algorithm that meets this specification:
c = 1000000000 x p + 10000000 x n + 1000000 x r
where c is ciphertext, p is plaintext (values 1 .. 26), n is position in
stream, and r is randomly either -1 or 1
But
c = E( n || p || 0 || 0) + 1000000 x r
where E is any good block cipher and || denotes concatenation, also meets the
definition (well, with high probability), but is pretty secure.
------------------------------
From: Nobody <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: 3 May 2001 13:30:00 GMT
Cristiano wrote:
>
> "Mike Rosing" wrote:
<snip>?
Is it good that m>p map on the curve?
Yes. The operation of multiplication is this:
mult(a, fx)
a = a << 1;
if(MostSigBit(a) == 1)
a = a ^ fx; // this removes the MostSigBit, forcing all values <fx
return a;
end
http://www.engsoc.carleton.ca/~jlcooke/c.c
Some C source code to test the GF(2^8) using fx=0x11B=1 0001 1011 can
be found there. There's some code demonstrating addition and
multiplication.
JLC
------------------------------
From: Jean-Luc Cooke <[EMAIL PROTECTED]>
Subject: Re: Message mapping in EC.
Date: 3 May 2001 13:31:50 GMT
Nobody wrote:
^^^^^^
This is ludicrous! I'm going to throttle him...
JLC
------------------------------
From: Rick Wash <[EMAIL PROTECTED]>
Subject: Re: DES sample vector
Date: 03 May 2001 09:59:52 -0400
[EMAIL PROTECTED] (Luis Duarte) writes:
> On Thu, 03 May 2001 07:31:11 GMT, =?iso-8859-1?Q?Fr=E9d=E9ric?= Donnat
> <[EMAIL PROTECTED]> wrote:
>
> >But i didn't manage to find an example describing the result for
> >each round. :-( So, if someone can point me to a site where i can
> >find an implementation having a dbug mode to see these result, i
> >would be very greatfull. ;-)
> >
> >Bests regards.
> >Fred
> >
>
> I don't remember where I got these sample vectors but I find them
> pretty useful.
I don't think this is it, but your post reminded me of it.
http://theory.lcs.mit.edu/~rivest/destest.txt
This is an interesting test vector from Ron Rivest.
Rick
------------------------------
From: Rick Wash <[EMAIL PROTECTED]>
Subject: Re: A Question Regarding Backdoors
Date: 03 May 2001 10:13:18 -0400
"Tom St Denis" <[EMAIL PROTECTED]> writes:
> "Tim Smith" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > On Mon, 30 Apr 2001 11:11:33 GMT, Tom St Denis <[EMAIL PROTECTED]>
> > wrote:
> > > Then he should ask the right question which is "Is it legal to
> > > use > 256-bit symmetric keys in the US". This has nothing todo
> > > with AES or possible
> >
> > That's not the right question. The right question is whether he
> > has to put a backdoor into his system, which is what he asked. No
> > one else seems to be having trouble understanding the question, so
> > the problem is you, not him.
>
> To me that's the last thing a serious cryptographer should be
> asking. Most have problems enough with inadvertant bugs that
> cripple systems (PGP, Netscape, etc...) let alone intentional bugs
> or faults.
No, it is not. At the very least, the US government has made some
very serious proposals for backdoors into cryptosystems. For example,
look at the proposed Key Escrow systems. One of the drawbacks of
these systems is that they only work if everyone plays by the rules,
and to get everyone to play by the rules the government will have to
outlaw non-backdoored crypto. If a serious cryptographer plans to
continue being a serious cryptographer, then he/she should be careful
to obey the law and not end up in jail.
I personally don't like the idea of having backdoors in my crypto
software, whether intentional or not, but when I write the software I
am careful to check and make sure that I will not end up in jail for
it. It is a very important question, and a good thing that he asked.
Better safe than sorry in a case like this.
Rick Wash
------------------------------
From: "Simon Hunt" <[EMAIL PROTECTED]>
Subject: Re: Avoiding bogus encryption products: Snake Oil FAQ
Date: Thu, 3 May 2001 15:20:48 +0100
The current Wassanar ruling is that if products are generally available
(i.e. over the counter, mail order etc), installable without considerable
assistance from the manufacturer, and include crypto not easily modifiable
by users, then they can be sold under the general software distribution
licence.
I think this holds for the whole of Europe now...
Simon.
"Henrick Hellström" <[EMAIL PROTECTED]> wrote in message
news:9cp46p$l4p$[EMAIL PROTECTED]...
> > ``Military Grade''
> >
> > Many crypto vendors claim their system is ``military grade.'' This is a
> > meaningless term, since there isn't a standard that defines ``military
> > grade,'' other than actually being used by various armed forces. Since
> these
> > organizations don't reveal what crypto they use, it isn't possible to
> prove
> > or disprove that something is ``military grade.''
> >
> > Unfortunately, some good crypto products also use this term. Watch for
> this
> > in combination with other snake oil indicators, e.g., ``our
military-grade
> > encryption system is exportable from the US!''
>
>
> A bit OT, but might be of some interest for some:
>
> This is in particular true regarding export of encryption software from
> Sweden (and most other EU countries I guess). Such export is primarily
> regulated by "Lagen om export av produkter med dubbla användningsområden",
> roughly "The act on export of products with double applications", i.e.
both
> military and civilian, e.g. nuclear technology. If your product is put on
> the list of products not exportable under that law, then either the
Swedish
> government or the EU commision considers your product to be "military
> grade".
>
> Just out of curiousity, does anyone know of any security software actually
> on this list?
>
>
> --
> Henrick Hellström [EMAIL PROTECTED]
> StreamSec HB http://www.streamsec.com
>
>
------------------------------
From: Gary <[EMAIL PROTECTED]>
Subject: RE: open source highscore server: impossible?
Date: Thu, 3 May 2001 10:43:22 -0400
One way is for the server to action replay the game that was played to
create
the score. This is OK for individual checks of very very high proposed
scores.
Also check if proposed score (and combination of numbers) in relation to
level
reached is possible in that game.
>===== Original Message From Marc Mutz <[EMAIL PROTECTED]> =====
>Hi!
>
>On the KDE (Unix Desktop) games development list, we are currently
>thinking about ways to provide
>
>a.) a per-machine highscores
>b.) (internet) highscore servers
>
>as opposed to per-user highscore lists. The problem is that most
>solutions that pop into the mind of the unwary allow easy cheating.
>While we think that - roughly - providing each game with a certificate
>at install time to authenticate against a setgid 'games' program and
>making the involved binaries executable, but not readable, thus
>preventing ptrace'ing of and poking-around in the binary, is enough to
>prevent cheating of every local user (except root, of course), this
>seems to not work for an internet highscore server that will collect
>highscores from users all over the world.
>
>The main problem seems to be that both the games and the highscore
>server are to be open source.
>
>Has anyone here an idea?
>
>Thanks,
>Marc
>
>PS: http://lists.kde.org/?l=kde-games-devel&m=98884330006288&w=2
>has the current proposal.
------------------------------
From: Sergei Lewis <[EMAIL PROTECTED]>
Subject: Re: open source highscore server: impossible?
Date: Thu, 03 May 2001 15:50:02 +0100
> The main problem seems to be that both the games and the highscore
> server are to be open source.
> Has anyone here an idea?
There seems no practical way of telling whether a score came from a real
program or a hack. This is probably related to the problem of
guaranteeing destruction of all copies of a piece of data.
You could aim to do some non-intensive score calculation serverside. The
problem would then seem to come down to telling a real game being played
apart from a fake one that's being staged.
For a turn-based strategy game, try logging a copy of all moves
serverside. The server can check the validity of the moves offline and
calculate the score itself. The server knows how the game AI would
respond to each player move, so can do random checks. I see little
potential for cheating.
For an action game, base all pseudorandom game decisions on a
server-supplied initial seed, a copy of which is stored serverside for
each game. Dump a log of the game decisions, player input, initial and
final state to the server afterwards. The server can then verify the
validity of the score, and the potential for cheating is reduced to
automating player input, which may or may not be acceptable.
--
Sergei Lewis - http://members.tripod.co.uk/~Folken
"I'm not falling - this is how I fly.."
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Reply-To: [EMAIL PROTECTED]
Date: Thu, 3 May 2001 15:16:48 GMT
Mark G Wolf <[EMAIL PROTECTED]> wrote:
: [...] what is this dynamic substitution of which you speak?
See: http://www.io.com/~ritter/GLOSSARY.HTM#DynamicSubstitutionCombiner
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: DSA in GF(2^W)?
Date: Thu, 03 May 2001 14:40:27 GMT
"Roger Fleming" <[EMAIL PROTECTED]> wrote
> >I'm not sure I follow. What public-key algorithm uses theory that is
> >over 2000 years old? Arithmetic is that old, but that's about all.
> You commit the common sin of unfairly deprecating the intelligence of our
> forebears. The ancient Greeks in fact made substantial inroads into number
> theory long before the birth of Christ.
> Ever heard of Erastothenes' Sieve, the great grand-daddy of all prime
search
> algorithms? Erastothenes died in 194 BC. (He is also the guy who
calculated
> the circumference of the earth with an error of only 1.4%). ...
Fine, but nothing on factoring, discrete logs, modular cube roots, etc.
I'll accept that the math of RSA was known to Euler and Gauss about
200 years ago. Perhaps a little older for discrete log systems. But not
2000 years ago.
> In short, the assertion that the mathematicians of 2000 years ago knew no
> number theory is completely wrong, and the assertion that they knew little
> more than arithmetic is offensively wrong.
Sure they knew some number theory and arithmetic. Maybe 0.01% of
what is known today.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: open source highscore server: impossible?
Date: Thu, 03 May 2001 16:23:15 GMT
On Thu, 3 May 2001 15:15:32 +0200, Marc Mutz <[EMAIL PROTECTED]> wrote, in
part:
>While we think that - roughly - providing each game with a certificate
>at install time to authenticate against a setgid 'games' program and
>making the involved binaries executable, but not readable, thus
>preventing ptrace'ing of and poking-around in the binary, is enough to
>prevent cheating of every local user (except root, of course), this
>seems to not work for an internet highscore server that will collect
>highscores from users all over the world.
>The main problem seems to be that both the games and the highscore
>server are to be open source.
I'm sort of confused here.
I would think that on an individual machine, it is indeed simple
enough to prevent anyone cheating with the high score of a game, if
the users don't have any access to the game except execute access, and
the game is run setuid or setgid to access the high score list.
But this wouldn't be relevant to an internet high score server, since
most people playing games on their home computers _are_ root on those
computers.
Quite a while back, someone asked a similar question, and I proposed
having the computations for a particular user's game done on two other
computers; if they match, this authenticates their accuracy, becaue
those two other computers would be chosen at random worldwide from
those currently playing.
This works for certain things, but not for games involving very high
speed computations which must take place on the user's own computer,
and which can be tampered with to affect scoring of the game. Trying
to certify the binary won't work, since the part of the program that
sends in the score can be tampered with to check a copy of the
original binary (so even a challenge-response key-dependent checksum
won't solve anything).
I think, though, that in your post you hinted at an idea that just
might work; I haven't looked at the current proposal yet, but maybe
this is what is being considered already.
You have three open-source programs.
One is the game, written in a higher-level language.
Another is a shell program, within which the game's binary executes.
The third is the compiler used on the game.
Although the game is open-source, one magic constant is "wrong" in the
source, and the distributed binaries are compiled with that constant
having a different value.
The compiler compiles the game into a sort of encrypted binary.
The shell program allows this binary to execute, and allows it to
communicate over the Internet.
One can verify the authenticity of the binary by checking for the
magic constant with a handshaking sequence.
The idea is tampering with the shell program won't allow the
handshaking sequence to work, because the right value is unknown.
Tampering with the game itelf again won't work, because no changed
version based on the source will have the right magic constant.
Why won't this work?
Because the shell program can be tampered with - if it allows
execution, it can be tampered with to become a disassembler for the
game, and hence the magic constant can be revealed.
And if the handshaking is done in P-code, but the game is done in
machine language, the shell program can be tampered with to use the
authentic copy for the P-code, but the tampered copy for the machine
language.
Having the P-code modify the machine language by repeated reading and
writing could be a barrier to this: if the P-code branches to the
tampered machine language (for easier play) but reads the good machine
language (for correct checksum) then a sequence like read machine
language instruction, add 20, write machine language instruction, read
machine language instruction, add another 20, write machine language
instruction will fail, whether writing is to the original copy or the
executed copy. But that kind of trick isn't really available in open
source.
And this assumes the P-code is too hard to dissasemble, also a weak
assumption.
John Savard
http://home.ecn.ab.ca/~jsavard/
------------------------------
From: Amr Youssef <[EMAIL PROTECTED]>
Subject: SAC2001 Final Call for Papers
Date: Thu, 03 May 2001 12:25:04 -0400
Final Call For Papers (SAC 2001)
--------------------------------
Eighth Annual Workshop on Selected Areas in Cryptography to be held at:
Fields Institute, Toronto, Ontario, Canada August 16-17, 2001
Workshop Themes
================
1. Design and analysis of symmetric key cryptosystems.
2. Primitives for private key cryptography, including block and stream
ciphers, hash functions and MACs.
3. Efficient implementations of cryptographic systems in public and
private key cryptography.
4. Cryptographic solutions for web/internet security.
Invited Speakers
=================
Phong Q. Nguyen, Ecole normale superieure, France
Moti Yung, CertCo, New York, NY, USA.
Program Committee
===================
Stefan Brands, Zero-Knowledge Systems, Canada
Matt Franklin, UC Davis, USA
Henri Gilbert, France Telecom, France
Howard Heys, Memorial University of Newfoundland, Canada
Hideki Imai, University of Tokyo, Japan
Shiho Moriai, NTT, Japan
Kaisa Nyberg, Nokia Research Center, Finland
Rich Schroeppel, Sandia National Lab, USA
Doug Stinson, University of Waterloo, Canada
Stafford Tavares, Queen's University, Canada
Serge Vaudenay (co-chair), EPFL, Switzerland
Michael Wiener, Entrust Technologies, Canada
Amr Youssef (co-chair), University of Waterloo, Canada
Yuliang Zheng, Monash University, Australia
Current Sponsors:
=================
CACR (University of Waterloo)
Certicom Corporation
CITO (Communications and Information Technology Ontario)
Ecole Polytechnique Fédérale de Lausanne
Entrust Technologies
ZeroKnowledge
Instructions for Authors
=========================
Submissions must consist of an extended abstract of at most 15
double-spaced pages, clearly indicating the
results achieved, their significance, and their relation to other work
in the area. Authors can either email
one copy of a Postscript file to [EMAIL PROTECTED] or send ten copies of
the extended abstract to
SAC 2001
EPFL - DSC - LASEC
IN- Ecublens
1015 Lausanne - Switzerland
Tel.: +41-21-693-7603
Important Dates
================
Submission Deadline May 7
Notification of Acceptance June 25
Workshop Dates August 16-17
Deadline for Proceedings September 16
Proceedings
===========
It is intended that the Proceedings will be published by Springer-Verlag
in the Lecture Notes in Computer
Science (LNCS) Series. In order to be included in the Proceedings,
papers must be presented at the Workshop
by one of the authors. As in previous years, the Workshop Record will be
available to participants.
For further information contact:
Serge Vaudenay, EPFL, [EMAIL PROTECTED]
Amr Youssef, University of Waterloo, [EMAIL PROTECTED]
Conference web page:
====================
http://lasecwww.epfl.ch/sac2001/
------------------------------
** 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
******************************
