i still don't get why people use elliptic curves instead of diffie-hellman since you can use it for public keys too. the index calculus cryptanalytic method appears to apply for the usage of F_q where q = pn for some prime p. it appears that if q is a large prime and q - 1 is divisible by a large prime, that covers the two biggest error cases
483
Replies
0
Boosts
@hipsterelectron DH and RSA are the canonical examples of vulnerable to factoring or discrete logarithm breakthroughs and surprise, that's exactly what Shor's algorithm does.
https://cr.yp.to/papers/safecurves-20240809.pdf if you read section 10 and onwards there are just an incredible number of problems arising from elliptic curves not using integer bit strings as points where it becomes incredibly hard to tell whether anything is a legitimate point and that seems like a huge problem
and furthermore the index calculus method is not very well evaluated + it seems to apply to elliptic curves anyway
The literature has many more examples of complications stemming from the interface gap between [bit] strings and elements of E(F_p)
this sounds like a bad protocol
Efficient bijections are known for some elliptic curves.
this is definitely not making the case
so because elliptic curve bullshit is confusing as shit the blockchain boys broke the foundational assertion against double-spending
As an illustration of the second complication, the Monero blockchain announced in 2017 [166] that it had patched a vulnerability allowing each coin to be spent 8 times. Monero used Curve25519, which has cofactor 8, so there are 8 points T ∈ E(Fp ) such that 8T is the neutral element; Monero’s security analysis was expecting a point P to be in the order-l group, but the software was accepting P + T as a separate expenditure for each of the 8 points T.
literally not a good protocol
at the end of this djb paper he essentially says yeah you can trigger arbitrary incorrect behavior due to the incredibly complex encoding between integer bit strings and elliptic curve points and nobody knows how to fix it
my suspicion has been for quite a while that DH is the easiest method to implement safely and efficiently and i have learned nothing about elliptic curves which indicate they are safer from index calculus other than daniel jackoff bernstein and miller the IBM guy saying so without really explaining.
having a clear mapping to bit strings and no invalid points is a pretty huge benefit and since RSA relies upon the same trick for encryption i feel this is sufficient for me to feel confident about my insane belief that elliptic curves are confusing on purpose
very funny wikipedia page https://en.wikipedia.org/wiki/Index_calculus_algorithm
The choice of the factor base size r is critical, and the details are too intricate to explain here.
from the koblitz textbook, the factor base depends upon the size of the prime p, which is why it's relevant for q = pn
The lack of the notion of prime elements in the group of points on elliptic curves makes it impossible to find an efficient factor base to run index calculus method as presented here in these groups.
so...nobody's found it yet
Likewise, there’s no known algorithms for efficiently decomposing Integers into members of a target subgroup.
yeah cause everything is obfuscated
first reference http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf
Due in large part to recent discoveries, discrete logarithms in fields GF(2n) are much easier to compute than in fields GF(p) with p prime.
the 1976 diffie-hellman paper literally says to use a prime smaller than a b-bit string so you can use machine integers
Hence the fields GF(2n) ought to be avoided in all cryptographic applications. On the other hand, the fields GF(p) with p prime appear to offer relatively high levels of security.
lol
It turns out, for example, that the MITRE scheme [38,59] and the Hewlett-Packard chip [69], both of which use the field GF( 2127 ), are very insecure.
MITRE and HP backdoored???? gasp
everyone keeps saying diffie-hellman key exchange is unauthenticated. this bell labs paper (sus) even goes so far as to claim there are "no private keys" in diffie-hellman. both of these are obviously wrong
@hipsterelectron
Sadly I have no clue about how diffie-hellman key exchange went. All I can remember is:
Alice wants to send payload to Bob.
Alice puts LockA on payload locked with KeyA.
Alice sends locked payload to Bob.
Bob adds LockB to payload locked with KeyB.
Bob sends payload back to Alice.
Alice removes LockA from payload using KeyA.
Alice sends payload back to Bob.
Bob removes Lock B from payload using KeyB.
Bob can now read the payload.
@hipsterelectron
okay I remembered now.
it was more like:
Alice uses the Public machine and her KeyA to create LockA.
Bob uses the public machine and his KeyB to create LockB.
Alice sends LockA to Bob.
Bob sends LockB to Alice.
Alice takes LockB and her KeyA, and turns it into the Shared Lock.
Bob takes LockA and his KeyB, and turns it into the same Shared Lock.
@meluzzy if you take a prime q and a base a which is a generator for the prime field F_q (i.e. if you repeatedly multiply a by itself mod q it will produce every element from 1 to q - 1) then you have this crazy identity that (a^x)^y (mod q) = (a^y)^x (mod q) for any x, y in [1, q - 1].
@hipsterelectron
A = g^a mod p
B = g^b mod p
s = B^a mod p
s = A^b mod p
this I remember, it blew my mind when I first learned about it.
@meluzzy it still seems fake 2 me
@meluzzy i was looking at this because i wanted to know if it could be used for a weird kind of checksum. i think it might?
@hipsterelectron My first (wrong) thought about it was that it must be like how when you XOR a value A with a value B you get a value C and then if you XOR that value C with the same value B, you get back value A.
@meluzzy XOR is good bc it's invertible! DH is kind of directional which is tricky so you have to design cryptosystems that leverage it. luckily it aligns really well with sending a message
@meluzzy particularly when you do in fact want the checksum to be commutative, like you might want with directory entries since those aren't order-dependent like file blocks
the 1976 DH paper is WILDLY negative about backdoored ciphers lmao
wow https://www-ee.stanford.edu/~hellman/publications/27.pdf didn't know diffie and hellman also said DES was brute-forceable like a year after it was standardized???
The cryptosystem is a FIPS (Federal Information Processing Standard) standard. binding on all applicable federal agencies. Because ASCII is also a FIPS standard, the plaintext data will often be represented as 8-bit ASCII characters.
there's everything there's IBM there's FIPS there's even NIST by its old name
In summary, we believe we have made a convincing argument concerning the insecurity and planned obsolescence inherent in the proposed cryptostandard.
planned obsolescence in 1977?????
@hipsterelectron Wow, that's a fascinating paper.
https://en.wikipedia.org/wiki/Advanced_Encryption_Standard a paper in 2015 has space complexity of cracking AES-128 down to 9 exabytes
https://en.wikipedia.org/wiki/Exascale_computing
On 29 July 2015, Barack Obama signed an executive order creating a National Strategic Computing Initiative calling for the accelerated development of an exascale system and funding research into post-semiconductor computing.[32]
This attack requires the attacker to be able to run programs on the same system or platform that is performing AES.
the way they dance around the subject of how "side channels" work while glazing up known evil bad guys like djb and shamir is crazy. it's not about "running programs" on the same system, but those programs being able to trigger cryptographic operations in response to uncontrolled input
it's so crazy that AES and block ciphers more generally don't mix up ciphertext across blocks??????
@hipsterelectron part of AES is that it doesn't need it. This also lets it be really fast.
@benjistokman sure but splitting the input into blocks and associating exactly one block key to each block of plaintext seems like it would make key recovery easier. splitting by varying chunk sizes and rearranging all the way across the message makes use of the additional structure of a fixed-length message that neither block nor stream ciphers can leverage
i'm pretty sure that's correct????
ChaCha is the basis of the BLAKE hash function, a finalist in the NIST hash function competition, and its faster successors BLAKE2 and BLAKE3.
finally this all makes sense to me
learning about checksums. i don't like em
@hipsterelectron checksum? I don’t even know um
MD5 was designed by Ronald Rivest in 1991
does this guy literally do anything other than backdoors
![[object Object]](https://media.mas.to/accounts/avatars/109/287/758/133/964/366/original/0f3099c0adfb36a0.png "[object Object]")
@hipsterelectron this cut is perhaps too specific, but Ronald Rivest is the name of someone who designs and opens a lightly themed casino in the 90s and then goes to prison 2 decades later for racketeering
There is a long list of cryptographic hash functions but many have been found to be vulnerable and should not be used.
i'm fucking amazed nobody has ever brought up the idea that checksums might be different for the purpose of integrity checking vs cryptographic signatures
@hipsterelectron
For the purpose of an integrity check it would actually be great if the checksum differences only slightly is the change in data is small
@realn2s i was thinking about this with i believe @heptapodEnthusiast and we were both kind of unsure how to achieve collision resistance without indifferentiability but i am pretty sure i figured out a cheat code for this and it is basically to retain the entire tree of hash computations at all times, and then invent a tree hash for directory trees:
for file hashes, use a tree hash like BLAKE3 (i'm making some tiny changes personally) and just retain the entire hash computation tree. this will take something like
C * log^2 nspace forC= chunk size andn= number of chunksfor directory hashes, we need two components:
- something to mix together the top-level checksum from the entry's content with the entry name string. since we really do want to catch name changes that don't change the content we will have to think harder here. maybe up to a certain name length we just store the whole name in-place along with the hash value. the point is to get a standard-size hash value we can cast into an integer
- we use modular exponentation (i.e. diffie-hellman) to commutatively hash the directory entries
that's it!
it should be possible to store the resulting hash tree in a fixed amount of space per directory entry, and you can limit the size of the transmitted hash tree by just stopping your bread-first search after some point
then you get a certificate that not only indexes into a remote object db, it's also self-certifying
@realn2s @heptapodEnthusiast this comes from the other thing i really wanted, which was to avoid having to recompute the whole hash tree upon change. so you can have a hash tree all the time with (hopefully) much less performance impact
Snixstoresnixstoresnix
@nobody they haven't made it into a filesystem or tried to go for kernel support at all which is ridiculous if you genuinely want ironclad semantics. the nix store also necessarily implies a global filesystem view which is terrible to optimize and it's also a failure of isolation. the reason making this faster might be useful is because every single process on the system is going to be bound to a named "domain" which is a managed filesystem view that can only share content across domains with a process that has access to both
@hipsterelectron
To be clear, I'm talking about snix-store specifically, which does lazy fuse+virtiofs (unfortunately not erofs) and merkle hashes, so very similar motivations. But I 100% concur on the annoyance part
@nobody i am very excited about making an improvement over merkle hashing >=] not in a way that will excite anyone but me though
@nobody it is like always perpetually my problem that i have to convince people what i've done is cool. happened when i forked signal and made a cli like gpg. i'm patient
@hipsterelectron
Didn't know pants considered fuse, will give Mathias a tip to consider a citation in https://arxiv.org/abs/2604.11398
@hipsterelectron
A got a hint from your thread... Looking forward!
@nobody i promise i'm not trying to hate on you personally here but it's incredibly annoying to me when nixers (it's specifically nix users) act like sandboxing is this sort of all-or-nothing trust relationship when sandboxing a process execution is basically the easiest part because you just use the OS tooling for that.
pants (i.e. me) had considered a FUSE fs for at least 5 years running but:
- FUSE is annoying to ship and very nonportable
- it still wouldn't let us manage IPC or task scheduling at all
- it absolutely doesn't give us persistence guarantees
the one thing it does do is let us virtualize i/o. but i think that's much better done by reaching into the guts of the compilers themselves and making them do i/o through my library
@nobody and if you have a fork of the compiler (but specifically one that does not change code gen in any way at all) then you (meaning me, who is doing an insane build tool that is not pants) can probably handle most of the other functions too
@nobody being a build tool or a package manager makes things a lot easier. build xor pkg is the motto
@hipsterelectron @nobody portage is crying in the corner