undefined | Better HN

0 pointsdragontamer2y ago0 comments

The opposite IMO, we're just bad at explaining it.

There's two strategies: substitution and permutations. Substitutions is when you replace a set of bits with another set of bits (ex: ABCD might become IAQN). Permutations is when you move bits around (ex: ABCD might become CADB).

When you mix substitutions with permutations, and then loop like 10+ times, it becomes really hard to follow. Bam, cryptography algorithms.

----------

How do you build substitutions and permutations that are hard to follow? Well, it seems like substitutions are the hard one, permutations seem relatively straight forward to me in most block ciphers (AES is really easy: a rotation to the right, and then a column-wide rotation. All of the bytes are in a 4x4 matrix, for the 16-bytes. Its actually super easy to follow AES's permutation steps).

Substitutions need to be done in such a way that is resistant to pattern-matching / cryptoanalysis. Choosing random numbers is not sufficient. For this, we enter "math", such as galois fields.

Galois Fields looks complex, but that's only because you haven't learned them yet. All a Galois Field is... is a set of numbers (such as 0, 1, 2, 3, 4, in the GF(5) field) that have addition, addition-inverse, multiplication, and multiplication-inverse.

Note: Galois Fields manage to accomplish this by reinventing the definition of addition and multiplication. Ignoring this... weirdness... its rather straight forward. Every operation can be inverted (not just addition and multiplication... but also complex algorithms like exponents, logarithms, square roots and more).

Once we're assured that both addition and multiplication can be perfectly inverted, we can build substitutions that are perfect... and then use math to prove that it should be hard to invert (though always possible to invert, due to both addition and multiplication having inverting-steps).

Proving that these things are "hard to reverse" with cryptoanalysis is beyond the scope of most student's study. So Cryptography courses go into Galois fields but forget to tell you why the hell you're studying it in the first place.

--------

In practice, we just show off AES's S-box (substitution box), that says which bytes get replaced with new bytes. And vice versa (https://en.wikipedia.org/wiki/Rijndael_S-box).

The GF(2^8) extension field just is a complex way of saying 8-bit numbers using this weird "addition-changed / multiplication-changed" math system that has guarantees of reversal / invertions.

0 comments

8 comments · 2 top-level

bawolff2y ago· 3 in thread

I'm confused, how is this not explaining math? That all sounds like math.

Not to mention this is basically an eli5 for what is a block ciphers (or aes specificly). If you are actually studying block ciphers you'll need to learn much more than that. Additionally, Block ciphers are just one part of cryptography - i think this thread was more about ECC.

dragontamerOP2y ago

All encryption, hashing, ECC, etc. etc. is about taking advantage of invertible operations.

Encryption needs to be inverted. So that's easy enough to understand. Hashing (and cryptographic hashes) need to be inverted because of the pigeon-hole principle. If we have a space of 1000 numbers, we want 1000 unique hashes to 'maximize the space'.

Turns out that the easiest way to accomplish this is through invertible functions, because if there's 1000 numbers that hash into 1000 other numbers, that's called a 1-to-1 and onto function, which is also the requirement for invertibility.

Any other setup, say 1000 numbers that turn into 500 numbers, weakens the hash obviously (two numbers collide for no reason), while the reverse 1000 numbers into 1500 numbers, is impossible.

---------

Once you realize that invertibility is the key to all of these algorithms, then its very straightforward. Its just a bunch of math that most simply accomplishes the goal.

The reason why crypto-math "looks" hard is because no one teaches the motivation behind the primitives. Its not like Galois Fiels are randomly used you know, mathematicians liked the properties of Galois Fields... and how easy it is to invert those operations.

bawolff2y ago

> Hashing (and cryptographic hashes) need to be inverted because of the pigeon-hole principle. If we have a space of 1000 numbers, we want 1000 unique hashes to 'maximize the space'.

This is non-sensical and false.

Hash functions are not invertible. They are not injective functions. The domain is much larger than their range. You can hash multi gb files and get a small fixed size result. Furthermore, the entire point of a hash function is to not be invertible

To be clear invertibility (and especially trap door invertibility) is quite important in crypto. After all - it is mostly the study of secret messages - no point to that if you cant unscramble the message.

However understanding the goal is not the same as understanding how it works and how it fails. There is a long journey going from invertible functions are cool to wtf is an eliptic curve. The point of a course in cryptography isn't to teach people just what a cipher does as a black box, but to teach them how it works under the hood.

> Its not like Galois Fiels are randomly used you know, mathematicians liked the properties of Galois Fields... and how easy it is to invert those operations.

If you mean in the context of aes s-boxes, Other block ciphers do not do that. The important aspect was their non linearity not invertibility. Any valid sbox is going to be invertible.

> Once you realize that invertibility is the key to all of these algorithms, then its very straightforward.

I'd be curious how you connect this to zero knowledge proofs

1 more reply

l33t2333722y ago

It seems like you have an issue with _how_ the math is explain, not _that_ the math is explained.

AlotOfReading2y ago· 3 in thread

It's hinted at in your post, but to make it more explicit we use GF(2^n) mainly because using it means arithmetic can be efficiently implemented with bitwise operations on digital computers. The whole mathematical machinery of modern crytography is a weird hybrid between the kinds of math computers can do quickly and the kinds of math that are easy to analyze for humans.

dragontamerOP2y ago

GF(2^n) Galois Field numbers are actually somewhat inefficient at multiplication. At least, in the 90s when AES was invented (today we have pmull and carryless-multiplication that speeds things up, but its still overall slow compared to normal multiplication).

Because of this, modern ciphers prefer Add-Xor-Rotate ciphers instead of Galois Field operations. As it turns out, Add-Xor-Rotate groups are provably invertible too, and are far, far more efficient to run than Galois Field operations.

adrian_b2y ago

Fast Galois Field operations are significantly cheaper to implement in hardware.

The only reason why they may be slower in software is because the Intel and AMD CPUs already had fast integer operations, but neither Intel nor AMD have bothered to also provide a fast implementation of carry-less multiplication on most of their CPU models (though on most recent models the speed is adequate for polynomial authentication done concurrently with AES encryption).

bawolff2y ago

I always thought that aes to prove to the world that the NSA didnt bribe people to choose bad random s-boxes. People used to worry about that with DES (turned out they actually changed the numbers of des to fix a not publicly known attack)

I dont see how aes use of gf(2^8) based sboxes have any implication for speed, but maybe i am out of my depth.

j / k navigate · click thread line to collapse

0 comments

8 comments · 2 top-level

bawolff2y ago· 3 in thread

I'm confused, how is this not explaining math? That all sounds like math.

dragontamerOP2y ago

All encryption, hashing, ECC, etc. etc. is about taking advantage of invertible operations.

Any other setup, say 1000 numbers that turn into 500 numbers, weakens the hash obviously (two numbers collide for no reason), while the reverse 1000 numbers into 1500 numbers, is impossible.

---------

Once you realize that invertibility is the key to all of these algorithms, then its very straightforward. Its just a bunch of math that most simply accomplishes the goal.

bawolff2y ago

> Hashing (and cryptographic hashes) need to be inverted because of the pigeon-hole principle. If we have a space of 1000 numbers, we want 1000 unique hashes to 'maximize the space'.

This is non-sensical and false.

> Its not like Galois Fiels are randomly used you know, mathematicians liked the properties of Galois Fields... and how easy it is to invert those operations.

If you mean in the context of aes s-boxes, Other block ciphers do not do that. The important aspect was their non linearity not invertibility. Any valid sbox is going to be invertible.

> Once you realize that invertibility is the key to all of these algorithms, then its very straightforward.

I'd be curious how you connect this to zero knowledge proofs

1 more reply

l33t2333722y ago

It seems like you have an issue with _how_ the math is explain, not _that_ the math is explained.

AlotOfReading2y ago· 3 in thread

dragontamerOP2y ago

adrian_b2y ago

Fast Galois Field operations are significantly cheaper to implement in hardware.

bawolff2y ago

I dont see how aes use of gf(2^8) based sboxes have any implication for speed, but maybe i am out of my depth.

j / k navigate · click thread line to collapse