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
34
Replies
52
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
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?????
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??????
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
MD5 was designed by Ronald Rivest in 1991
does this guy literally do anything other than backdoors
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 take a look at International Standard Content Code (ISCC)
https://www.iso.org/standard/77899.html
@lavaeolus @realn2s i am terribly fascinated about the ISO standard even thought it seems i cannot at all get a hold of it. i have a few concerns with some statements on this blog.tib.eu post however:
- it is EXTREMELY strange to be mentioning MD5 as if it were an "exact cryptographic hash", in 2024 of all years:> (We have been using a similar MD5 checksum in the details of objects for decades, e.g. in many media or document repositories).
there is no discussion nor mention nor link to discussion about what constitutes a cryptographically secure hash function. MD5 has been known to be broken against second preimage attacks for at least two decades. it was also designed by ronald rivest who seems to only make US government backdoors and nothing else.
i normally would not emphasize this this much, i just feel it is so shockingly negligent to write that it was worth noting. SHA-256/SHA-512 should be widely available and are fine even if i like different ones. the issues with merkle-damgård constructions like SHA-1 and SHA-256/512 are mostly a problem if you're signing data or keeping some other thing secret.
@lavaeolus @realn2s i generally have a huge set of issues with fuzzy hashing (the same issues i have with compression) and don't believe it can be done without a domain expert who can dictate the data layout of a file and describe the structure of it mathematically so that you can even identify the data ranges to calculate the patch against.
because really even my very length mechanism here with storing the whole checksum tree is just about calculating a diff at the end of the day. so this blog post seems extremely credulous of
This type of application is not new, research has been going on for decades – the only thing that is new and important for our context is that a workable specification has been agreed internationally as a standard for an identifier.
i think it is possible to define a specification for this to some degree (it would allow me to calculate a minimum patch for my version control / filesystem idea). so maybe they've done just that. but i get very antsy about the idea that "oh, it's been stuck in research, now it's ready for us". if people get too comfortable with the slop hash and then use MD5 for the "cryptographic" hash that would be a major cause for concern
@lavaeolus @realn2s yeah this page they linked is more clear https://web.iscc.io/
Create experimental ML-based Semantic Code (images and text only).
slop hashing
Per-chunk fingerprints of text — enables matching fragments inside a document.
this is actually what i want to do for my filesystem / version control tool, so that's totally good. but idk why it's disabled by default
@lavaeolus @realn2s this part deeply confuses me
ISCC is a pure object identifier that is not intended for resolving, i.e. accessing, the object in question.
it is absolutely not widely understood, but a cryptographic signature is generally the same thing as a checksum, and generally it just computes a checksum then does something else to the result. so it's just very strange that they're asserting that the identifier for integrity cannot be used to resolve. i don't understand why
@lavaeolus @realn2s cynically, i would say it's because anyone can create an integrity identifier, whereas DOI registration is highly centralized. wonder what @jonny thinks about the above, goodness knows i'm not even an expert on cryptography
i do absolutely think it would be possible to develop non-slop ontologies of major data formats so that we could get really meaningful diff calculations. that's something a bunch of motivated people could totally do (i was thinking of making it a feature in my version control tool that could be implemented oni a per-repo basis). so i am 100% about the idea of hashing that conforms to document structure, and i think it's totally never been done before afaict
@lavaeolus @realn2s @jonny ohhhhh yeah so
The strength of the ISCC in the context of scholarly publishing and cultural heritage lies not least in its ability to automatically identify a definable work retrospectively.
this is major major surveillance vibes. and that's absolutely one thing hashing can be used for
Proprietary similarity hashes, such as those used for many years by database providers such as Google Scholar,
with full disrespect this is absolute fucking bullshit. they're using fucking n-grams everyone uses fucking n-grams. the only "proprietary" part about it is all the servers google owns. great paper from the literal NSA on n-grams https://dl.acm.org/doi/10.1145/256163.256168
For example, machine learning models could use these ISCC codes to register their training data, thereby achieving a higher level of trust and reliability.
this is very very specifically saying "running their training data through the machine we may or may not be using for surveillance". it is not something the machine learning model would want at all (it would identify copyrighted/illegal content, for example). so maybe the people who advocated for MD5 are exceptionally clueless or maybe they are hungry for hashes. they do seem extremely jealous of google and that's not a good sign
