B,TMSR~ Block Cipher Competition
The Mosti Sereneii Republic, reunited in congress, decided :
- That all presently known block ciphers suck ;
- That an actually useful block cipher is required for our own purposesiii;
- 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 :
- 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.
- Use a 64 kbyte key.
- Fits In Headvi
- 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.
- 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!
———- Moreso than anything else. [↩]
- This denotes that it is sovereign. [↩]
- Which are, quite transparently, the destruction of any other pretend-sovereign and the enslavement of its supporters. [↩]
- Citizenship revolves around presence in the WoT. [↩]
- The difference between works and "works" is best illustrated by the discussion of keccak. [↩]
- 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. [↩]
- 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 cipherasciilifeform 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.
[↩]
- If you are unsure as to how this sort of submission should ideally look, djb's excellent salsa20 page should provide some good pointers. [↩]
Thursday, 4 February 2016
I propose abused-RSA (or Cramer-Shoup!) as block cipher!
Can haz 10btc ??
Friday, 5 February 2016
If it ends up accepted, yeah.
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.
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 ?
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?
Saturday, 6 February 2016
You're certainly not supposed to keep the key in your head, good grief.
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.
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.
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
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 ....
Saturday, 6 February 2016
You will notice that cryptography isn't a programming skill anymore than marketing is.
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.
Sunday, 7 February 2016
Ever heard of Turtle cipher?
Monday, 8 February 2016
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!!!!
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.
Monday, 8 February 2016
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.
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.
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.
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.
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
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.
Tuesday, 5 December 2017
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 ?
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.
Tuesday, 30 October 2018
How about using keccak as a key expander?
Given a message M of size m and a key K, the enciphered message E = M xor keccak(input = K, output size=m).
M is then retreived as E xor keccak(K).
Works with any key size and message size you want.
Tuesday, 30 October 2018
Your systematic dedication to lowerst-possible-effort "contributing" is starting to make you sound very much like the Romanian morons.
This is even useful, after a fashion, in that it shows there's nothing specifically Romanian about the Romanian morons in question, but that their sad state is merely the necessary result of systematically following a stupid strategy (something I, and as far as I know I alone, always suspected).
Because in the end that's how you build, Romanias and Uruguays and any other Orcistan : by systematically being you, by making your sort of committments to the saeculum and then attempting to adapt the Republic to them "as best one can", which is to say without waking up the insignificant other in the other room.
It doesn't work, lay off it.