it feels incredibly trippy to be reading about quantum physicists (an evil science) using group theory (a lovely beautiful field misused by the horrors) to do just their normal average everyday sort of evil as opposed to the horrors
65
Replies
0
Boosts
so i'm learning that neural nets are also precisely the kind of thing you would create to calculate discrete logs
also learning that the guy stallman fell over himself to defend against any allegation was potentially the most average MIT "AI" loser ever
https://en.wikipedia.org/wiki/Marvin_Minsky
While working at Bell Labs in 1952, Minsky proposed a design for a useless machine he called the "ultimate machine". When switched on, a device emerges from it to switch it back off. Claude Shannon, Minsky's mentor at the time, built the first working prototype.
@hipsterelectron
I wanted to defend the Useless Box, but I'll take “Death of the Author” for $100.
https://en.wikipedia.org/wiki/Marvin_Minsky#Association_with_Jeffrey_Epstein
@dzwiedziu i cannot possibly express enough that this is a frighteningly recurrent theme among evil cryptographers
@dzwiedziu i was surprised i didn't know anything about him but the epstein shit and then stallman defending him and his wikipedia page is much less decorated than other turing award winners (they quite literally do not give you a turing award unless you are a shockingly evil human being)
![[object Object]](https://media.mas.to/accounts/avatars/109/287/758/133/964/366/original/0f3099c0adfb36a0.png "[object Object]")
@hipsterelectron I’m learning a lot about John McCarthy lately and it’s really not looking good for the “you can’t say all AI is bad” people
@zzt yeah just flip the classifier 1 - Bad(AI) = oh huh i've never seen it produce that many zeroes without a decimal point before
@zzt @hipsterelectron “McCarthy spent most of his career at Stanford University.” Is all you need to know about him really
https://en.wikipedia.org/wiki/Stochastic_Neural_Analog_Reinforcement_Calculator
hmmmmm
Prompted by a letter from Minsky, George Armitage Miller gathered the funding (a few thousand dollars) for the project from the Office of Naval Research of the U.S. Department of Defense in the summer of 1951 with the work to be carried out by Minsky, who was then a graduate student in mathematics at Princeton University.
GRADUATE STUDENT IN MATHEMATICS AT PRINCETON UNIVERSITY
like this is so much more likely to be a cryptanalytic hardware module. in 1951???? that was barely out of world war 2. i don't know why that would need to be hidden
this is from the princeton dean in question and he specifically said einstein disproved this prof's theory about planetary orbits like that was einstein's fault. princeton is so bad dude this is like a parody
This comment is unavailable — it may have been deleted or is not visible to you.
He was an expert in mass spectrometry by which isotopes of an element could be separated according to their mass but not by any chemical means as they are chemically identical. A typical mass spectrometer consists first of a source in which the sample is ionized so that it has a charge and can be accelerated to form a beam. This beam is directed into a perpendicular magnetic field, which makes the constituent particles move in a circular path. The radius of the circle depends on the particle mass, so that the lighter ones move in a smaller circle than the heavier ones and are thereby separated.
he goes into this incredibly lengthy description of all the parts of the mass spectrometer except the one i care about which are the mechanisms to record ion counts since that's the one that lies to you and only returns an opaque statistical estimation
you can't possibly pretend to be a physicist and act like the part where it counts single fucking electrons isn't the coolest shit ever. we were going to start writing our own analyses at the cancer lab if we were able to get access to the counters
oh he made a corporation selling mass spectrometers no wonder he wouldn't mention that bit
he studiously avoids ever explaining any of the electron/ion measurement devices. what a strange quirk
oh my god dude this is in the new yorker https://www.newyorker.com/magazine/1981/12/14/a-i
I have known Minsky for more than thirty years. When I first met him, in the late nineteen-forties, at Harvard, it was not entirely clear what his major academic field was—or, perhaps, what it wasn’t. He was taking courses in musical composition with the composer Irving Fine. Although he was an undergraduate, he had his own laboratories—one in the psychology department and one in the biology department—and he was writing what turned out to be a brilliant and original senior mathematics thesis on a problem in topology.
i can't fucking believe this i didn't think he would actually be so radioactively obviously doing evil mathematics
i'm gonna find his thesis
https://dl.acm.org/doi/pdf/10.1145/321328.321337?download=true
Unrecognizable Sets of Numbers (1966)
and he literally cites our boy rabin too
The technique described in this note enables one to show that certain sets cannot be recognized by finite state automata
GOD FUCKING DAMN IT IS THAT WHY AUTOMATA THEORY SUCKS TOO
We consider here only the binary representation, so as to avoid pompous statements, but the same results can be obtained for any radix by changing all 2’s to r’s in the sequel. We warn readers not to confuse the statement that the primes written in binary form are not a regular set with the trivial statement that the set of strings of prime length is not regular.
this is just the discrete log problem?????
If
a_nis of odd length,2k+1, it has the forma_n = b_n 2^{k+1] + d 2^k + b_n, wheredis0or1.
this also gives the q = 2p + 1 relation??? this is also an actual analysis of the appropriateness of discrete log as a CSPRNG???
@hipsterelectron I mean... the whole CS base curriculum kinda sucks. to me, one main reason is that we do "CS" rather than "informatics" in the first place.
@promovicz well i recently learned that all of the people i hate who literally without exaggeration work for the israeli genocide apparatus (chomsky working for MIT means he is very much included, MIT is the problem) were all central to the development of "formal languages" as a field. it makes perfect sense how i was able to develop completely novel work without any prior expertise
@hipsterelectron as a hacker since youth i can't pass this by as "con theory". it's certainly real that "MIT is a problem" (sic) - and some people might do well to remember RMS/FSF history. i have no doubt that "special talent" gets special treatment. i have no doubt that cryptography research involves politics. about the rest, i can't really draw final conclusions - but i can proceed with reasonable assumptions.
@promovicz i fervently believe there was a concerted effort to deskill and disengage academic study in operating system development (worldwide!!!) after the late 90s and most certainly to do the same for cryptography and other forms of mathematics since well before then (it began around the late 70s but really took shape in the 80s with ECC created soon after RSA, because modular exponentiation alone was in act too powerful and easy to understand). but i'm actually more concerned about basic symmetric cryptography. NIST limiting AES to 128-bit block size while varying key size was an incredibly dirty trick and they knew it
@promovicz and of course this means parsing must be denigrated and discarded as a field of investigation or research, which means compilers and programming languages pass that on to their users, and it means vulnerabilities, everywhere, because parsing is definitionally the system's boundary with external input.
@promovicz there's very much a reason the turing machine employs a tape, and it's because it was expected to recieve input, and process it, and produce output, and this was supposed to go to the user. and mark rabin (who called dibs on formal languages, and cryptography earlier) would strike the first gruesome and contemptuous blow against the turing machine, with extreme prejudice
@hipsterelectron i would love to know the reason for TM construction "with tapes", or good modern arguments for the choice, because i've been wondering.
for my own models, i'm undecided whether input/output memory should be separate, or just seen as the same memory with different constraints on the in/out side.
@promovicz it's the simplest general model. the framing that a turing machine's purpose is to transform the tape is completely fucked. that's not the point at all. the point is that you have mutable state, some of which you can set aside, and other sections that can grow freely. the restrictive nature of the single tape works specifically for problems that work like implicit graph traversals. you can and should add on whatever else you want. a stack or two is always a good idea (although two stacks is really more useful for things that do parse strings)
@promovicz the problem comes when you start handwaving away logarithmic factors for larger machines and processes. in many cases you may have a problem that you can verify won't grow in memory past a certain amount: modular exponentiation in the forward direction is an example where the turing machine makes it excessively simple to make strong claims about runtime, particularly since bignum arithmetic conforms so naturally to the tape that moves one at a time.
you should not be feeling like the turing machine constrains you. make a better model if it works. you can do that too. the turing undecidability paper was to prove undecidability exists, similarly to how modular exponentiation is almost a kind of joke to demonstrate one-way functions (mostly) exist (i need to do more group theory to maintain safety everywhere).
hellman claims the choice of q = 2p + 1 is specifically to trade off between exponential computation and exponential memory. i haven't found a good proof for this yet, but the idea deeply compels me. you can make the enemy dance for you. they can't touch you.
@hipsterelectron yes - i don't feel constrained by the Turing model at all, because we have a reasonable understanding of its equivalences (imo). my open question on "programs as transforms" has its origins in information theory, and the idea that programs don't necessarily answer/solve specific problems (which is a traditional premise i'm poking at).
@promovicz i promise i'm not hating on you personally but i absolutely fucking hate the word information theory it just makes me too pissed off to use about my own work anymore. reading this paper about how much simpler kolmogorov's model had been for decades with painstaking work to piece together the pieces bell labs shit out was so important to me https://projecteuclid.org/ebooks/berkeley-symposium-on-mathematical-statistics-and-probability/Proceedings-of-the-Fourth-Berkeley-Symposium-on-Mathematical-Statistics-and/chapter/Mathematical-Problems-in-the-Shannon-Theory-of-Optimal-Coding-of/bsmsp/1200512168.pdf
@promovicz the complexity basis behind secure modular exponentation can be viewed from a computational perspective and a data and memory perspective. both of these are necessary at once for crypto, e.g.:
a^x = b (mod q)- [represented as a bitstring, therefore as
[0, 2^{k}]], wherek = floor(log_2 q) - 1, - hellman said you can actually perform
floor(log_a k)squaring operations here (for reallog_a), not justfloor(log_a q), and such squaring becomes faster here because you can make it a bit shift. the state you keep track of here is just the remaining squares!
so this was half of it. this is the computational view. now we bring in what i call the dataflow view.
for example:
- if
a < sqrt(q), do we "lose" some information here? what is divulged? what abouta < cubert(q)? [i saw these two roots in succession in in a number theory textbook yesterday somehwere]
but immediately we then must break out some level of group theory, because typically while q - 1 is a generator of F_q, the other cycles are smaller (and if not a cycle, they may branch out elsewhere). which produces a much less random sequence than then used in solution. and the group theoretical approach gives us ridiculously more power to analyze these and essentially to mitigate them, because it can make statements about the size of possible generating groups at the start
i still can't say yet what exactly made hellman concerned enough to write that second paper on q = 2p + 1. to me, this is largely still mediated through the smaller groups, but i can't say much about those yet.
consider another example, from "symmetric" crypto (although i absolutely hate that term as its because by definition it's literally not symmetric
i don't fully know what any of the SHAs does and BLAKE3 is even worse as it is literal djbware. here's a question i posed earlier: how much "information" (which i may deem the integral of "data) is being ignored in these cases:
- read each byte at a time, left to right (the standard)
- reading in blocks, and proceeding always left to right
- unrestricted: taking advantage of not just that the end of the message is later than all the earlier tokens, but also the same kind of local information that something like AES with a counter mode like AES-GCM achieve. at the same time!
@promovicz i have a really terrible symmetric algorithm based upon the final point, and as you may have [intuituted it works by squaring or something, in fact, without workiing too hard by spliting it halfway, and following the point of some .
there's a curious connection.! in the forward [heroic] direction, modular expentiation, we wanted to force our adversity to perform some maximum form of work which coulld not be replaced or amortized. of course you know of the CSPRNG use case for discrete log -- i am now working to understand and determine the subcyclic behavior so that we achieve both computational and informational unguessability.
now consider an insecure system: you could break e.g. the key scheduler for the AES-encoded message. but (speakiung abstractly here) you cannot invert the transformation uniquely at all without the key for my half-assed cipher, because it mixes and modifies data across the entire length of the message, and the message is also a cyclic group if you go both directions, outwards from the center! and i fully believe this is in fact capable of (if certainly not now) the precise unconditional security that claude shannon was so stumped on.
you could also establish the cross-influence upon the key and the message and determine more specific bounds, according to a model of computation and (if you're careful) an "oracle" or "game" experiment with bounded security failures.
dataflow serves as a kind of "conservation of energy"-like principle for me to design safe systems. one reason i despise the "probabilistic turing machine" is because it directly makes excuses and cheats auditors of the author's clever notation. but for discrete log, there is a fundamentally serial computation required to factor the largest subgroup of q - 1. and that is in fact how you can achieve security. and the turing machine happens to represent that alright in many cases
@hipsterelectron i don't do cryptog actively at the moment because "stress avoidance" - but i do think these are worthy angles. it's sad that this is a loaded subject.
@hipsterelectron *swoops file to ePaper tablet* - yes, i see the point that it's an unclear term, and it gets unseemly when discussing non-determinism in my discrete case. it also seems incomplete/incoherent when dealing with non-discrete mathematical objects.
i could maybe say "discrete information metrics"? have an idea?
@promovicz oh it's not about clarity, the word is clear enough. my issue with it is the misuse of it for half a century by bell labs and IBM and EVERYONE WHO WANTS TO MAKE A FILESYSTEM BECAUSE THEY LOVE HAVING POWER OVER OTHERS AND NOT SEMANTIC GUARANTEES!
@promovicz i also don't believe discrete is fully capacious
@promovicz i have heard somewhat convincing arguments (from kolmogorov, and another coding theory paper i have somewhere) that continuous information is often more capacious than the discrete.
i would say discrete is an appropriate representation of finite and fully reproducible capacity/memory.
to me, the thing being measured/tested/implicitly employed to send messages tends to take the form of a continuous representation. this may be more of a bias about keeping an open mind/etc, but i also believe it's necessary for any system existing in a physical universe with the arrow of time.
for example, while double ratchet does avoid requiring any auxiliary messaging back and forth to maintain chain state (good, since it's not forced to produce a known-plaintext attack), that also means the two users can be progressively starved of responses during an active denial of service, while continuing to generate new chain keys without any new external randomness from the expected DH inputs!
furthermore (and this is something i want to work with dr. sasha boldyreva on), the diffie-hellman secret being tied precisely to a single message (even without DoS/starvation in play) also means you can't "prepare" or "stock up". and it also means an attacker knows the exact times when you'll refresh your chain (i.e. when to influence your incoming or outgoing data/RNG). with that in mind, we might like instead to treat the diffie-hellman shared secrets not quite as discrete and ephemeral inputs, but as a mutual storehouse we can refer to, along with our own RNG to select from this.
this would entail thinking a lot harder about whether it would make it easier for one participant to sabotage the other, but the continuous representation is i think the right one in this case!
@hipsterelectron excellent point wrt "information theory". in my mind, we know for a fact that machines that are discrete in both time and value, are less universal than the universe, and cannot realize the same algorithmic complexities as continuous systems. examples: bead sort, soap computers, wave interactions, three-body-problem.
@promovicz to be clear, you're not handwaving away any logs, but every single person in the entire world saying DH is cracked due to lenstra's basis factoring algorithm is knowingly handwaving away a log factor
@promovicz my parser compiler achieves several great things--one of them is identifying regular and single-stack components of your input grammar (these must be real requirements from the grammar, they're not imposed), as well as minimizing the impact of undecidability to a specific paired stack loop (if the ratios of stack diffs go quasiperiodic or chaotic, it may never halt. but in that case, you can limit iteration to just that one loop, and literally lose zero functionality).
the model i chose there was in fact a single-stack machine by default, because that makes it easy to express progress and termination conditions, and because my grammar compiler separates out and analyzes the lengths of stack cycles beforehand. and then calculating stack differentials pairwise to cross out incompatible inferred token states (generated at the beginning of the parse) takes a familiar form--it's actually not a turing machine, it's much more like calculating a rational approximation, and it just zips together stack diffs to merge adjacent sub-parse graphs. termination for fixed-length input occurs when the sub-parse has hit bound boundaries.
add a second stack is actually really easy and not a bad thing to do in general. it's generally pretty obvious when it's going to cause trouble, and it's not the framework's job to make that decision for the user. two stacks are also really easy to analyze for termination conditions in most cases, and you can often rearrange your stack operations without much difficulty to ensure (e.g.) that you schedule the ones that don't have bad behavior first (e.g. so your system does not loop endlessly on a failing fixed point).
i absolutely recommend using your own models at all times. i personally very much like the turing machine if we're looking to make claims about number or graph-theoretical problems, but it has always been a canard from rabin/rivest/MIT grads that "the turing machine doesn't incorporate [something i haven't even tried to codify methodically so a turing machine could use it]", which is an excuse for google to say "because we're such big scale, we have to fuck up and waste money all the time". that's what animates me about it.
@promovicz the US was always always one to choose submitting its youth and future mathematicians and scientists and shakespeares to lasting trauma instead of empowering them to do anything at all, and the IETF of course demonstrates they know very well how a backdoored system lets everyone else in.
i noticed france and IRIA quickly turned on the hero louis pouzin during precisely the year the diffie-hellman paper was released: 1976, a year after our "church committee" revealed the NSA's existence and its program of widespread surveillance under nixon. and they shut down his CYCLADES network, which unlike the internet protocol actually fucking worked.
and of course 50 years later in 2026 we find daniel j bernstein and tanja lange at TU eindhoven working tirelessly to ensure nobody else implements cryptography but them, and they lie profusely, all the time, and continue to be trusted to develop protocols and standards for the rest of the world. who benefits from this?
@promovicz i was terribly sad to have inferred just earlier that in fact the main rationale for the prominence of neural nets is that marvin minsky worked specifically to break cryptographic codes for the US government, and large amounts of linear algebra are how you can break the most secure RNGs and diffie-hellman itself.
and of course (nobody else cares about this for some reason) signal is very clearly aware of this, and their new cryptographer has decided to move not just to lattice methods (which are so ridiculously unserious i can't fucking believe anyone can read any paper on them and not feel sick) but indeed to create a whole new protocol from scratch based on them! and immediately moved all users too.
check out page 60 (the very last page) of the new protocol https://eprint.iacr.org/2025/078.pdf
lattice methods in cryptography are just an excuse to perform more matrix multiplication. dwork's first paper on the subject very specifically describes matrix multiplication to invert a system of equations as one possible mode: this is very specifically the work necessary to break a discrete log cryptosystem.
![Adversarial randomness. Another line of work, e.g. [ACD19, HKP`21, BFG`22a, AJM22] assumes
that the adversary gets to fully control the randomness.
As argued by Balli et al. [BRV20], the additional power of each corruption model does reflect to certain
real-world attacks. For instance, there are certain real-world attacks that randomness leakage does not
capture, but that is captured by adversarially chosen randomness. While thus appealing, we argue that the
third model is problematic when considering post-quantum security: For realistic choices of parameters, most
lattice-based KEMs are not perfectly correct, implying that an adversary choosing the randomness can induce
arbitrary decryption failures. For “ratcheting” protocols that continuously exchange fresh key material, such
correctness issues moreover can translate into security issues, if it allows the adversary to tamper with the
decryption of a freshly exchanged public key.
Several countermeasures are conceivable:
• One may choose parameters in a regime where perfect correctness is guaranteed for lattice-based scheme.
While this approach was taken in the initial (theoretical) post-quantum instantiation of the Double
Ratchet in [ACD19], this ultimately is highly undesirable for practical applications where the size of
post-quantum keys is one of the main obstacles towards adoption.
• One may harden the randomness as part of the cryptographic protocol. For instance in [HKP`21] the
authors generate the randomness via an output of a hash function. In the ROM, one can then prove,
using a union bound argument, that the probability of the adversary finding bad randomness triggering
a decryption failure is negligible (cf. [HKP`21, Section 1.3]).
In this work we eschew the issue of adversarially chosen randomness and choose the model of honest-butleaked randomness instead for several reasons. First, the model already captures many of the attacks from
bad randomness. In particular, this captures the exposure of all intermediate values of a computation during
a corruption. (In contrast, if an attacker only gets to see the state between operations and the operations
can use fresh randomness, intermediate values may remain hidden.) Second, while a real-world attacker
may realistically have some control over the randomness source, arbitrarily setting the randomness (but not
allowing to tamper with other protocol state) seems to be an extremely strong assumption not met by the
real-world attacks pointed out by [BRV20]. Finally, randomness hardening should preferably be performed at
the operating system level and not the at the level of an individual cryptographic protoco](https://asset.circumstances.run/media_attachments/files/117/173/612/331/601/291/original/a29a5aebb7eb2cef.png)
@promovicz imagine having a safety guarantee against adversarial RNG, and throwing it away. throwing it away!
@hipsterelectron how is there even an argument here, in "countermeasure 1"!? in my mind, key generation and encryption should be less intertwined to begin with...
@hipsterelectron i own physical books on Cyclades, because uni keeps throwing away good books.
who benefits? well... "lots of people in specific parts of the world".
@promovicz thank you oh my god that makes me very emotional please keep them safe and that includes inside your mind as well as in solid form
@promovicz i got my pouzin book from the naval research library. i'm trying to keep as many pieces as i can
this is the author credited with simultaneous discovery of the discrete log CSPRNG? https://en.wikipedia.org/wiki/Cobham%27s_theoremQ
this is his discrete log paper https://sci-hub.red/storage/moscow/658/cd1020ccc6e42c54cacbcdacde0be189/cobham1969.pdf
https://en.wikipedia.org/wiki/Cobham's_thesis it's really fascinating too that the other 1974 phd thesis from dillon came about (as best i can tell) from digital multichannel radio transmissions in which one desired a long carrier wave (i think lengthier waves let you fit more channels in or something?) anyway that thesis was the first time i'd seen a fourier transform expressed as a matrix which recorded the frequencies of each cyclic subgroup and it all worked in the integers because it was (mod m)
and then the author was explicitly like ok JUST for this one bit i'm not gonna be looking at this as a number but JUST as a function operating upon a string of bits (i.e. a bit vector with independent components) and i was like ohhhhhh sick and he was like yeah we're seeing what the cardinality is or whatever
i often find matrices terribly aggravating when they look like assigned work even if i really like drawing my little number friends in their little n x m box houses looking out their little windows
it was really cute and fun to read too. he would always have these adorable little adjectives preceding statements he was proud of https://drum.lib.umd.edu/items/d8150b1f-1bdd-4c3d-9987-c14a95251edc absolutely ace mathematician vibes
@hipsterelectron oi! they say "fourier analysis of boolean functions". That's really kinda "cute" in an academic sense, and I think it's funny how CS and math are different about researching fundamentals. We often end up with mathematicians writing about CS fundamentals, and CS not reading them, while math avoids its own fundamentals (because "no budget"). We're really on the same boat...
he did in fact thank the department of defense (Thank you Meta!)
but i had absolutely zero group theory background before reading and it's just. when someone is clearly writing with clarity and expertise and empathy you just get the hang of it pretty quick. and like observe too the author's application of jargon (he uses it: that is to be expected from a dissertation) and how different it is from when someone invokes jargon to signal
this really was so much like how my parsing work had turned out. now just gotta focus in on phd apps and spin a tale about filesystems crypto and i/o
