sci.crypt "Sandbox" [Was: Re: Small streamcipher MiniTrixor 48-bit]
From: Richard Heathfield (dontmail_at_address.co.uk.invalid)
Date: 08/30/03
- Next message: castello: "ldap for certifcate"
- Previous message: J. Campbell: "Re: BitBox PRNG"
- In reply to: Michael Brown: "Re: Small streamcipher MiniTrixor 48-bit"
- Next in thread: Hubert von Jättekivastjärna Sr.: "Re: Small streamcipher MiniTrixor 48-bit"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Sat, 30 Aug 2003 12:12:00 +0000 (UTC)
Michael Brown wrote:
> "Richard Heathfield" <dontmail@address.co.uk.invalid> wrote in message
> news:biof3a$rdf$2@titan.btinternet.com...
>> Michael Brown wrote:
>>
>> > Oh, by the way, the sci.crypt sandbox (name changes welcome, someone
> just
>> > called it this on the group and it's sorta stuck in my mind ...)
>>
>> You can send me the royalty cheques any time in the next week or two.
>
> You can have any advertising revenue :)
Oh. ;-)
> Each cipher will have two scores: one for how "good" it is and one for the
> number of points someone gets for a break. The reason for this is that
> breaking a ciphertext only challenge is more difficult that breaking an
> algorithm-known one (so I think should bre rewarded more) but a
> ciphertext-only cipher has less chance of being secure compared to a known
> algorithm one if both have been standing for the same time.
I suggest the following system:
The cipher-designer must post four ciphertexts, each of which has been
encrypted with the /same/ key. (This effectively eliminates One-Time Pad
entries, which is just as well, since nobody wants to waste their time on
those.) I suggest that you require them to submit these ciphertexts as four
separate binary files, named ciphername[1-4].cip. Each ciphertext should be
generated from a plaintext exactly 1024 bytes in size (but need not itself
be 1024 bytes long). The idea here is to make it possible for crackers to
develop software tools that will be reusable from one entry to the next,
rather than constantly having to adapt their tools to a plethora of lame
formats.
In their submission, they *must* also include all four plaintexts. You don't
post this, though - you just use it to validate cracks.
You probably want to reward a designer for the following behaviours:
Full and clear disclosure of algorithm, ideally in language-independent form
and with as little jargon usage as possible
Worked example of algorithm
Reference implementation in portable language
Suggested points awards:
Between 0 and 5 points for full disclosure, depending on the quality
(clarity) of the description.
Between 0 and 5 points for a worked example that adds value (clarity!) to
the disclosure.
Between 0 and 5 points for a ***working*** reference implementation, capable
of both encryption /and/ decryption, in a well-known language. What I
suggest you do is allow crackers to tell you which languages they are
sufficiently familiar with, keep a language familiarity tally, and allow
the full 5 points if the reference implementation is in one of the five
most familiar languages (provided it works, of course).
This gives you a total of somewhere between 0 and 15 points. If the
ciphertext supplier has correctly given you four ciphertexts generated
according to the above rules, add 1 to this figure, to give you a total of
1 to 16 points. This is the algorithm's score-per-week. As you can see, it
massively rewards a well-documented algorithm.
Maintain a "running balance" for each algorithm. When a break or partial
break occurs, three things happen:
the cracker is rewarded by N points
the running balance is decreased by N points
the cipher's score-per-week, if positive, is reduced
> I'm not quite
> sure how to handle different levels of breaks either: if someone makes a
> distinguisher for a particular cipher, then some time later someone
> figures out a chosen plaintext one, how should points be distributed? My
> current idea is to break the total points up so that a distinguisher is
> worth 10%, a chosen plaintext worth 20%, known plaintext worth 20%, etc
> etc. If you develop a chosen plaintext attack and noone has figured out a
> distinguisher, then you get 30% of the points, but only 20% if someone has
> already developed a distinguisher.
First to distinguish output (or keystream, which is effectively the same
thing) from random: 5% of cipher's remaining balance (rounded up), cipher's
score per week then reduced by 1 if possible (it should never go negative,
but can be 0)
First to produce a chosen plaintext break requiring no more than 64 bytes of
chosen plaintext: 10% of cipher's remaining balance (rounded up), cipher's
score per week reduced by 2 if possible
First to produce a known plaintext break requiring no more than 64 bytes of
known plaintext: 15% of cipher's remaining balance, cipher's score per week
reduced by 4 if possible
Complete breaks:
A cracker who can break one text should have no problem breaking all four,
but his method might be mildly time-consuming and he might prefer to submit
a partial break. So you could score it like this: count the number of
ciphertexts hitherto unbroken for this cipher, divide it into the number of
(hitherto unbroken) ciphertexts this cracker has just broken (call this
ratio R), and give him that portion of the remaining balance for the
cipher. The cipher's score per week is then multiplied, of course, by (1 -
R).
(Optional adjustment: the break might not get 100% of the text, so consider
allowing partial scores, proportional to the number of correct bytes,
provided at least 25% of the text has been broken correctly, without regard
to case.)
If no algorithm was posted, the cracker's score for this break is doubled,
and this extra score is "paid for" by the cipher's running balance. (This
is the only way a cipher's score can be reduced below 0.)
Worked example:
J Random Cryptographer submits four ciphertexts, each of which, he assures
you, has been generated from a 1024-byte plaintext. (If he is later
discovered to be lying, his cipher gets 0 points, period.) He produces a
pretty decent description of the algorithm, for which you decide to award 4
points. He also gives two worked examples, which make up for the mild
deficiencies in the explanation, so you give him another 3 points for that.
He provides a reference implementation, but it can't decrypt, so he gets 0
points for that.
Add 1, giving him a points-per-week of 8.
Nobody bothers looking at his algorithm for several months, and by week 20
he has a very respectable 160 points. Then Mallory demonstrates that, if he
is able to ensure that the first 8 bytes of plaintext are "MZMZMZMZ", he
can decrypt the rest of the message. He gets 10% of 160, or 16 points, for
this crack. These 16 points are "funded" by the cipher, which drops to 144
points, and its points-per-week are reduced from 8 to 6.
By week 25, the cipher is up to 174 points. At this point, Eve realises that
nobody has distinguished the output from random yet. She quickly does so,
and gains 5% of the points, which comes to 9 (we round up). Eve gets her 9
points, and the cipher's score is reduced to 165. Its score-per-week drops
to 5.
Three weeks later, Mallory is back. He has cracked one of the ciphertexts
correctly, and used this crack to work out the key, but he makes a mistake
in his calculations, and only one of his posted plaintexts is correct.
The cipher's current score is 180, and until now none of the posted
ciphertexts have been cracked, so Mallory gets a quarter of these points
for his single break: 45 altogether, raising his score to 61. The cipher's
balance is reduced to 135, and its score-per-day is multiplied by (1 -
0.25), so it becomes 5 * 3/4 which is 3 (after rounding down).
Two weeks later, with the cipher's score having risen to 141, Eve notices
that she can adapt Mallory's method to get the correct key, and publishes
the remaining three plaintexts. She gets all 141 remaining points, and the
cipher is now dead (0 score, 0 points per week.) The cipher peaked at 174
points.
Clearly, ciphers will slip down the "league table" as they are cracked, but
it might be interesting to keep a separate table showing the peak score
attained by each cipher. This would give cipher designers a little more
motivation to do well.
You will undoubtedly maintain a "cracker's table" too. Jim Gillogly should
of course carry a significant handicap, or be banned altogether, unless the
number of cipher entries becomes too large and exceeds his capacity.
Otherwise, there'll be less incentive for the rest of us.
>
> Suggestions are very welcome!
Oh good. ;-)
-- Richard Heathfield : binary@eton.powernet.co.uk "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999. C FAQ: http://www.eskimo.com/~scs/C-faq/top.html K&R answers, C books, etc: http://users.powernet.co.uk/eton
- Next message: castello: "ldap for certifcate"
- Previous message: J. Campbell: "Re: BitBox PRNG"
- In reply to: Michael Brown: "Re: Small streamcipher MiniTrixor 48-bit"
- Next in thread: Hubert von Jättekivastjärna Sr.: "Re: Small streamcipher MiniTrixor 48-bit"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
