B,TMSR~ Block Cipher Competition

Thursday, 04 February, Year 8 d.Tr. | Author: Mircea Popescu

The Mosti Sereneii Republic, reunited in congress, decided :

  1. That all presently known block ciphers suck ;
  2. That an actually useful block cipher is required for our own purposesiii;
  3. That we will consider proposals from barbarians as well as citizensiv.

Consequently, you are cordially invited to submit a proposal for a block cipher that :

  1. Worksv on block sizes of 1 kbytes, 4 kbytes, 16 kbytes and 64 kbytes. Bonus points for ciphers that work on an arbitrary block size.
  2. Use a 64 kbyte key.
  3. Fits In Headvi
  4. Items which come with a proof of hardness, as well as items that eschew basic arithmetic operationsvii as implemented by computers will be particularly favoured.
  5. While we will consider purely theoretical proposals, items which come with sample implementation and assorted tests will be preferred.viii

The rewards will be a 10 BTC payment from me, as well as a honoris causa position in the very Lordship. Let the party begin!

———
  1. Moreso than anything else. []
  2. This denotes that it is sovereign. []
  3. Which are, quite transparently, the destruction of any other pretend-sovereign and the enslavement of its supporters. []
  4. Citizenship revolves around presence in the WoT. []
  5. The difference between works and "works" is best illustrated by the discussion of keccak. []
  6. This means that the intelligent reader can hold the entire item in his mind at the same time. In this sense Fermat's theorem is an example of FIH, even if the proof hardly qualifies ; whereas Maxwell's original equations are not an example of FIH, even if Heaviside's restatement is. []
  7. To understand this point, the relevant discussion :

    mircea_popescu asciilifeform if you feel like entertaining some crackpottery, suppose a hash function defined as follows : a) calculate PM ; pM ; P!M ; p!M where P and p are the perimeters of polygons of M sides circumscribing and inscribed respectively in the same circle and !M is the bitwise negation of M ; b) calculate V1 = 2pMPM/(PM+pM) ; V2 = sqrt(pMPM) ; V3 = 2p!MP!M/(P!M+p!M) ; V4 = sqrt(p!MP!M) ; c) calculate H = (V1 - V2) * (V3 - V4) and finally d) return blocksize digits from the key-th position in H. how'd you go about attacking this ?

    asciilifeform I would have to think about it. But Gauss could prolly tell you right now! Wake'im up.
    mircea_popescu lol. (basically - they're the classical (Archimedan!) approximations of Pi, for the text and reversed text, to an arbitrary precision. Makes for an eminently tunable hashfunction).

    asciilifeform Terrible hash function. Bailey, Borwein, & Plouffe.
    mircea_popescu Do you see what I did here ?

    asciilifeform (IIRC Plouffe was the worker bee and the other 2 were parasites).
    mircea_popescu It is apparently a lot easier to follow math in words than in symbols, EVEN FOR YOU.

    asciilifeform Actually I am writing it out in symbols!111111 Why the bitwise negation ?
    mircea_popescu HA! You took a second to answer after my 2nd line, minutes after the first produced nothing! Timing attack on your brain!

    asciilifeform Clearly!1
    mircea_popescu Anyway - being able to calculate Pi itself does not actually help here, because we're specifically collecting the noise of the formula against the text and its mirror, rather than Pi itself. Hence the substractions.

    asciilifeform The root ops go poorly with bit arithmetic.
    mircea_popescu So they do. GOOD. Fuck the fucking computing-centric paradigm in crypotography. It's your tool not your fucking master.

    asciilifeform Then let's have the candle.
    mircea_popescu No. It's your tool, it must be used.

    asciilifeform Then you're stuck with wandering decimal crud. And titanic lookup tables, etc.
    mircea_popescu Sure. Anyway bignum operations is a solved problem. Even in Lisp.

    asciilifeform 'even' l0l
    mircea_popescu :)

    asciilifeform But decimal soup is still ick
    mircea_popescu Good.

    asciilifeform You won't have repeatable output.
    mircea_popescu So ?

    asciilifeform No repeat, no decrypt.
    mircea_popescu Hash function not cipher

    asciilifeform Then works.
    * mircea_popescu is still curious to hear how people'd attack, if anyone cares. Esp re preimage.

    asciilifeform I will prolly care. on the train, some time soon.
    mircea_popescu The reason I give it is mostly didactic. It plainly shows what I mean re proper use of math and treating your computer like a tool to do a job rather than treating your job as something to be adjusted to fit the computer - without having to delve into complexities and subtleties of number theory etc. Something as commonplace as "use the intervals of confidence of a polynomial method to estimate a transcendent" is really good enough. And it exhibits all those important properties : such as, you can ~actually~ use infinite message, and you can also use any arbitrary padding you like, up to infinity - the hash function won't complain. And you can want it to shit out any block size you want it to shit out - also won't complain, but give EQUALLY MEANINGFUL results. Whether you ask for 3 or 13 or 294 digits.

    asciilifeform I am quite certain that you knew this, but pretty much all published block ciphers date to the dark ages, when transistor was painfully expensive
    mircea_popescu I do. Still, some points have to be made. REPEATEDLY. Also, this is NOT a block cipher, but anyway.

    asciilifeform Age of cheap transistor had a faux-renaissance where folks used the cheap transistors for elaborate self-delusion - 'this is sooo complicated, nobody!1111 could crack', which led to a pile of corpses and a reaction.

    mircea_popescu Quite. Whereas the correct solution is to stick to the math. computers are fucking tractors not farm designers.

    asciilifeform Which enemy, naturally, took full advantage of. And here we are, somewhere after this.

    []

  8. If you are unsure as to how this sort of submission should ideally look, djb's excellent salsa20 page should provide some good pointers. []
Category: Bitcoin
Comments feed : RSS 2.0. Leave your own comment below, or send a trackback.

20 Responses

  1. I propose abused-RSA (or Cramer-Shoup!) as block cipher!

    Can haz 10btc ??

  2. Mircea Popescu`s avatar
    2
    Mircea Popescu 
    Friday, 5 February 2016

    If it ends up accepted, yeah.

  3. Jonathan Wilson`s avatar
    3
    Jonathan Wilson 
    Friday, 5 February 2016

    This is NOT the right way to design a block cipher. The AES contest that gave us the current AES block cipher is a far better way to design a block cipher.

    Every candidate for AES was thoroughly scrutinized by a bunch of cryptography gurus to make sure it was secure. And unless some major cryptographic breakthrough has been made that I didn't hear of (or someone has built a working Quantum Computer and managed to keep it secret from the whole world) AES still cant be cracked in any meaningful length of time.

  4. Mircea Popescu`s avatar
    4
    Mircea Popescu 
    Friday, 5 February 2016

    Here's the list of imbecilities you commited in five lines :

    1. "This is NOT right!11", reasons omitted.
    2. "My favourite team (that I don't play on) beats your team (that you play on), notwitstanding the 0-9000 score so far because fantasy sports league in my head."
    3. "Guru-isms matter in crypto, because this is a sort of yoga."
    4. "I can't even name the fucking gurus, but that's ok - if you can put up with my inability to list reasons, why should an inability to list authorities matter."
    5. "Everything is fine as it is, because I'm not a cow living in a carefully designed pen, but Jonathan Wilson himself!"

    What are you, some sort of an idiot ?

  5. Chris Dodd`s avatar
    5
    Chris Dodd 
    Saturday, 6 February 2016

    Requirements 2 and 3 seem impossible to meet simultaneously -- I certainly can't keep a 64K key in my head. Why the requirement for such a huge key?

  6. Mircea Popescu`s avatar
    6
    Mircea Popescu 
    Saturday, 6 February 2016

    You're certainly not supposed to keep the key in your head, good grief.

  7. Anne Williams`s avatar
    7
    Anne Williams 
    Saturday, 6 February 2016

    Could you be clearer on the key size, please? You cannot be asking for an *effective* key size that large, because humans are unable to reason reliably about computations larger than about the square of anything attempted. So even 256-security guarantees are suspect. Larger claims are purely wishful thinking.

    On the other hand, it's easy to create a key derivation function that takes arbitrary sized input. But we need to know the desired *effective* key size.

    Except for the desire for a block cipher, Keccak comes close.

  8. Mircea Popescu`s avatar
    8
    Mircea Popescu 
    Saturday, 6 February 2016

    Yes, I can, and I am in fact asking for an *effective* key size that large.

    What humans can or can't do is a topic for another time, but generally speaking the list includes flight, as well as flight with devices heavier than air, as well as flight with devices heavier than air at speeds that exceed the speed of sound, as well as flight with devices heavier than air at speeds that exceed the speed of sound taking place outside of Earth's atmosphere.

    For the sake of conversation let me point out that you may find the discussions around keccak as preserved in the logs interesting.

  9. Sandy Harris`s avatar
    9
    Sandy Harris 
    Saturday, 6 February 2016

    I designed a cipher called Enchilada for the CAESAR competition. It did not make it into the second round.
    https://aezoo.compute.dtu.dk/doku.php?id=enchilada

    A cipher in that class seems to meet many of your requirements. It does have a rather nice proof of hardness, and depending why you think "all presently known block ciphers suck", this might be one that doesn't.

    Provided your mental diagram facility allows black boxes for things like an existing block cipher or stream cipher -- I used ChaCha and Rijndael, but any ciphers could be used -- the rest of the Enchilada construction will fit nicely in your head; it is really pretty simple.

    I defined Enchilada for 128- or 256-bit blocks. Extending it to 512 or 1024 is trivial; just use the 512-bit cipher from the Whirlpool hash or large-block versions of Threefish. Going beyond that, which I am not convinced is necessary, would need a block cipher with big enough block size. The only off-the-shelf ones I know of are Xtea (there are published attacks) and Hasty Pudding (which by itself meets many of your requirements):
    https://en.wikipedia.org/wiki/Hasty_Pudding_cipher

  10. Mark Ramirez`s avatar
    10
    Mark Ramirez 
    Saturday, 6 February 2016

    The "we accept barbarians" got my attention ;-)

    Anyway cryptography is NOT one of my strong programming skills,
    yet, precissely, that's why I got some independent, out of the box,
    think different ides, abot cyphering ....

  11. Mircea Popescu`s avatar
    11
    Mircea Popescu 
    Saturday, 6 February 2016

    You will notice that cryptography isn't a programming skill anymore than marketing is.

  12. William Jones`s avatar
    12
    William Jones 
    Sunday, 7 February 2016

    http://journals.aps.org/prx/pdf/10.1103/PhysRevX.4.011026

    I haven't done the footwork but it seems to me that this model could be converted to provide a hash instead of encrypt. At first blush it seems like it would be nearly impossible to modify the data and still maintain the coupling in a way the receiver would accept.

  13. Iodilitiodo`s avatar
    13
    Iodilitiodo 
    Sunday, 7 February 2016

    Ever heard of Turtle cipher?

  14. Do you have an explanation in English for your rather bold claim that "all presently known block ciphers suck"? (And by "known" do you mean "the ones that you've heard of", or are you claiming some kind of encyclopaedic knowledge of this domain?)

    I mean, SHA-2 has only been around a decade and a half, and has never been cracked past a few dozen bits, but sure, it SUCKS, whereas some bullshit you came up with when you were stoned OBVIOUSLY has to be better, because so many decades of research have been done on that type of approach.

    Look, some high-school kid comes up in the newspaper every few years. "They invented a new super cool form of cyptography using something they learned in high school." Sure, all these methods kind of basically work, sure, they scramble bits and shit, but they never get used because nobody trusts them, because the high-school student can't do the cryptography legwork required to demonstrate that they're even slightly secure. Are you really expecting SOMEONE ELSE to do this legwork for you, based on your own stupid ideas, for a measly 10BTC? HA!!!!

  15. Mircea Popescu`s avatar
    15
    Mircea Popescu 
    Monday, 8 February 2016

    > Do you have an explanation in English for your rather bold claim

    It's not a claim, it's a statement. A claim is what a powerless entity makes before another in a position to judge. A statement is what a powerful entity makes before another not in a position to judge. Your situation here is not that you are in a position to judge and enjoy a differential of power, but exactly the reverse. As such your impudent pretension to the contrary is not going to make you any friends. Please make an effort to learn to behave in polite society before you word in its direction.

    Uncharacteristically, I did look through the rest of your message. There's nothing else there. Your father should be very ashamed of himself.

  16. Eddie and the other Eddies:

    In the 'so many decades of research', point us to an example of something that actually distinguishes, e.g., AES, from '... high-school kid comes up in the newspaper every few years. "They invented a new super cool form of cyptography [sic] using something they learned in high school."'

    In terms of mathematical proof of hardness.

    And skip the appeals to authority, and other cognitive stop-signs for pliant idiots.

  17. Mircea Popescu`s avatar
    17
    Mircea Popescu 
    Tuesday, 9 February 2016

    Turns out two comments were eaten by the spam filter, I've fished them out.

    @Sandy Harris This sounds like a composition scheme, is it ?

    Certainly a block cipher with large blocks would require a block cipher with large blocks. That's exactly the idea here.

    @William Jones Meh pdfs.

  18. Sandy Harris`s avatar
    18
    Sandy Harris 
    Saturday, 13 February 2016

    Mircea: Enchilada uses a form of composition; Use the stream cipher to generate whitening for the block cipher.

    It is not vulnerable to most of the usual attacks on stream ciphers. They start by using known plaintext & matching ciphertext to get a keystream sample. That won't work here unless the block cipher is horrendously weak.

    It is not vulnerable to most of the usual attacks on block ciphers. They require multiple blocks encrypted the same way & here the whitening changes for every block.

    The security proof is based on the Even-Mansour analysis of the XOR-permutation-XOR structure. I claim that with fairly mild assumptions -- the block cipher is a non-linear permutation and the stream cipher is not appallingly bad -- this construction has a provable lower bound on its security level: 2^b where b is the block size of the block cipher.

    That claim needs analysis & I'd love to see some.

  19. Mircea Popescu`s avatar
    19
    Mircea Popescu 
    Saturday, 13 February 2016

    You should probably join #b-a and discuss the security proof there with the resident cryptozoologists. In general whitening is dimly regarded, but the claim of a lower bound on security will be very interesting.

  1. [...] discovery and exploitation. [↩]To replace SSH entirely. To be based on the eventual winner of TMSR's cipher competition. [↩]The grammatical singular implies nothing about actual implementation. [↩]Mention of [...]

Add your cents! »
    If this is your first comment, it will wait to be approved. This usually takes a few hours. Subsequent comments are not delayed.