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.

23 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.

  20. Mircea Popescu`s avatar
    20
    Mircea Popescu 
    Tuesday, 5 December 2017

    As per the logs, the window of opportunity here turns out to have been 22 months (February 4 2016 to December 5th 2017), an interval during which the republic failed to produce the required item. We are consequently more idebted to tradition than we needed to be or should have been.

    I would hope this bitter lesson will be informative in the vein of

    mircea_popescu !~later tell apeloyee hey, do you want a job working for minigame ?
    jhvh1 mircea_popescu The operation succeeded.
    asciilifeform had nfi minigame had jobs etc

    mircea_popescu why not ? i've been trying to hire a bunch of artists for what, 5 years now ? the one thing teh republic doesn't lack is jobs.
    asciilifeform i suppose the word has >1 meaning

    mircea_popescu like what ?
    asciilifeform well we dun have so many, afaik, 'fix X, get Q btc' sort of job.

    mircea_popescu we have tons. starting with "fix your tits, get 0.02 btc" and from there on.
    asciilifeform other than the tits
    asciilifeform do i know about any of this ?

    mircea_popescu http://btcbase.org/log/2017-12-02#1745610
    a111 Logged on 2017-12-02 22:02 mircea_popescu i've been trying to hire a bunch of artists for what, 5 years now ?
    asciilifeform artist auditions are different item than the one in the q where 'fix x... get..' neh

    mircea_popescu asciilifeform you personally for instance http://btcbase.org/log/2016-12-27#1591437 ; to quote from teh very boardroom of minigame earlier, " noa. evident ca idealu' ar fi fost ca tata asta sa fi fost gata facuta din 2016, cum discutasem initial cu stan. da'... sufletu'."
    a111 Logged on 2016-12-27 22:14 mircea_popescu course since the nsa consulting work for minigame is going to produce ada rsa, it might be an idea to have an ~ada~ tmsr crypto lib.
    mircea_popescu ie, it'd have been nice to have this item done last year as per original discussions. but whatever.
    mircea_popescu asciilifeform there's no difference. artists dun wanna work, ie ON TIME and TO SPEC and ON WHAT THEY'RE TOLD TO just like erryone else.
    asciilifeform actually now that i think about it, mircea_popescu had a crypto bounty thing also
    asciilifeform for symmetric ciphering
    asciilifeform can't turn up the link for some reason

    mircea_popescu the amount of jobs awaiting workers exceeds the amount of availavble workers by a factor never before seen in human history ; not even during the saudi reign 20 years ago. not even in china. nowhere.
    mircea_popescu take for instance http://btcbase.org/log/2017-11-22#1742032
    a111 Logged on 2017-11-22 11:41 RagnarDanneskjol: mircea_popescu I may have someone worth inviting to chan for interview in the coming days. Most of the folks I know over there are primarily oral translators, so having to look around a bit. Just got back yesterday - BJ is a real shithole but the people are adorable, lots of good duck. FYI - 'VPN AC' (Romanian) seems to be the only one working well/consistently behind the firewall (I've used many) and
    mircea_popescu has it yet been A YEAR since the discussion of hiring a motherfcucking chinese office girl was tabled ?
    asciilifeform finally did dig up the first mention of proto-ffa in l0gz : http://btcbase.org/log/2016-06-09#1479552
    a111 Logged on 2016-06-09 22:06 asciilifeform i discovered that mainstream finite field libs are as complicated as they are largely because they insist on growable - and, ergo, heap-allocated - nums.
    mircea_popescu where the fuck is the office girl ?
    mircea_popescu etcetera.
    asciilifeform !~seen RagnarDanneskjol
    jhvh1 asciilifeform RagnarDanneskjol was last seen in #trilema 1 week, 3 days, 10 hours, 32 minutes, and 21 seconds ago: RagnarDanneskjol Everbright Bank has, by far, the lowest entry barriers for business or tourist visitors opening new accounts.

    mircea_popescu and yes, i'd much rather pour a coupla bitcents into the ground instead of paying "hiring experts" etcetera. by very far. at least when i pour it into the ground, i know what i'm doing with it as i do it. consider this schmucktard : http://btcbase.org/log/2017-10-11#1724165
    a111 Logged on 2017-10-11 20:40 BHopkins: I had to look up the current price, and the answer is yes :)
    asciilifeform what about him

    mircea_popescu nobody in his line of work has EVER made a bitcoin's worth in one year no matter what they did. but does he have enough sense to go... hmmm... i'll treat this as an advance, and use it to finance my supposedly useful work coming back with deliveries worth at least 10x that, because thaty's how useful i am, and see what happens. so... no. white man is lazy and stupid, in whatever order. the problem's not the lack of jobs. the problem's the 3rd world whore's attitude, as described in that friday piece. but otherwise -- everything's sough. you got tits ? make money. you can code ? make money. you can draw ? make money. you "got relations" / can pr/whatever the fuck you got ? MAKE MONEY! "oh but mp... really... i can't do anything, not usefully, not well, not within pre-glacial timeframes, not... not..." riight,
    asciilifeform glacial at least beats nuffin... asciilifeform so far only glacial .

    mircea_popescu http://trilema.com/2015/these-fools-have-been-handed-a-technology-so-clever-so-disruptive-and-revolutionary-that-the-rulers-of-the-world-would-have-to-fully-unmask-themselves-as-ruthless-tyrants-in-order-to-suppress-it/#comment-123721 << this stupid bitch, can be arsed to spam trilema by hand, can NOT be arsed to read anything. everyone, including the very last hopeless african in the throes of death by innanition imagines th emselves a process designer. ima, dontcha know, follow the funnel they constructed, like everyone's got an apple concept store. what, and write them emails ? why. who the fuck are they, and who the fuck am i, and who adapts to whom ? recall that schmuck with the french isp, which upon examination turned out to be 0% isp and 100% a vehicle for the inept vanities and worldviews of a few idle and overcomfortable schmucks ? it's all that, all the way down.
    asciilifeform the cocks thing ?

    mircea_popescu no, recently, some grenoble thing.
    asciilifeform the one davout dug up ?

    mircea_popescu or for that matter just as recently, some german dork, the dude with fucking options and self-determinations as to who he wants to work with. all of it, however wrapped, however excused, it's the same thing : we here in white man world are incapable of doing anything useful and don't wish to see why this'd make any difference.

    even though I don't really expect much more, or much other than the traditional response. Because people are valuable and important and whatever the fuck hallucinated nonsense.

  21. I feel rather stupid now for having played in a contest without a time bound declared in advance.

    Out of curiosity, do you intend to use Serpent forever, even after a well-founded TMSR replacement appears ?

  22. Mircea Popescu`s avatar
    22
    Mircea Popescu 
    Tuesday, 5 December 2017

    What would the need for a replacement look like ?

    For instance, I have no intention to ever upgrade the eulora crypto lib currently being brewed. I don't believe in upgrades, nor really ever have. So in this sense, there's no need for a symmetric cipher anymore, Serpent won.

    There is some space for an alternate, perhaps stronger, crypto lib for usage in a republican replacement of GPG, for which FFA looks like a strong basis (and where the much belated Cramer-Shoup implementation may have a good home). It is possible this may want a symmetric cipher for some purpose, but honestly I expect it will be in the vein of (if not likely exactly) MPFHF, which is to say algorithmic rather than algebraic. If at all present, which seems altogether improbable currently.

    In short -- there was not so much known demand for this category of item, and it missed out on the little that there was.

  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.