Compute a hiding of the identifier in JavaScript

Implementations Web
1

I got this question from @olehhrib :

I presented a demonstration:

  1. Download the secp256k1.js (2.5 KB) compiled from Paul Miller's typescript code.
  2. Create a demo.html with the following code:
<html>
<head>
    <script type="text/javascript" src="secp256k1.js"></script>
</head>
<body>
<table>
    <caption>Cryptographic Hiding</caption>
    <tbody>
    <tr><th>x_value</th><td id="x_value">Click "Calculate" to calculate</td></tr>
    <tr><th>y_value</th><td id="y_value">Click "Calculate" to calculate</td></tr>
    </tbody>
</table>
    <button onclick="
    // 0x5ff is ol**.g***.u*@gmail.com Keccak-256 hashed
    hashed_i = BigInt('0x5ffeb9a40ee8c14b5af808c6de5863469ce5ea7933bda393f70ca138a8b2d3c3');

    // privacy key value (not Ethereum private key value)
    privacy_key = 26577169521080041468048461869858263792019104904445492498349147139819994214859n
    hiding = G.multiplyDA(hashed_i).multiplyDA(privacy_key);
    document.getElementById('x_value').innerText = hiding.x;
    document.getElementById('y_value').innerText = hiding.y;
    ">
        Calculate
    </button>
</body>
</html>

You should now be able to use the "Calculate" button to calculate a hiding. Note hat the value for the hashed identifier as well as the privacy key are hard-coded in the HTML file.

2

I have not checked the source-code from Paul Miller, but on the surface that part looks good.

However, the following line unfortunately can lead to attacks:

The reason being that what is computed in hiding is actually

hiding = G^(hashed_iΒ· secret_p)

This means that an adversary can pick an arbitrary value hashed_i' and find a matching value

secret_p'=hashed_i · secret_p · hashed_i'⁻¹

s.t. hiding= G^(hashed_i'Β·secret_p').

To fix this, it is crucial that the hashed_i is actually the point we use for the computation, i.e. that hiding=hashed_i.multiplyDA(secret_p). We can construct a curve point from hashed_i using the following java code (taken from the blockchain-attestation repo in class AttestationCrypto.java):

  /**
   * Compute a specific point on the curve (generator) based on x using the try-and-increment method
   * https://eprint.iacr.org/2009/226.pdf
   * @param params
   * @param p The size of the underlying field
   * @param x The x-coordiante for which we will compute y
   * @return A corresponding y coordinate for x
   */
  private static ECPoint computePoint(ECCurve params, BigInteger p, BigInteger x) {

    x = x.mod(p);
    BigInteger y, expected, ySquare;
    ECPoint resPoint, referencePoint;
    do {
        x = x.add(BigInteger.ONE).mod(p);
        BigInteger a = params.getA().toBigInteger();
        BigInteger b = params.getB().toBigInteger();
        ySquare = x.modPow(new BigInteger("3"), p).add(a.multiply(x)).add(b).mod(p);
        // Since we use secp256k1 we use the Lagrange trick to compute the squareroot (since p mod 4=3)
        BigInteger magicExp = p.add(BigInteger.ONE).divide(new BigInteger("4"));
        y = ySquare.modPow(magicExp, p);
        // Check that the squareroot actually exists and hence that we have a point on the curve
        expected = y.multiply(y).mod(p);
      } while (!expected.equals(ySquare));
      resPoint = params.createPoint(x, y).normalize();
    return resPoint;
  }
3

In the protocol, the goals of the privacy key 𝑝 and one-time key 𝑝' are both for hiding H(𝑖), where 𝑖 is known to both Alice and Bob. 𝑝 is Bob's secret to hide H(𝑖) and 𝑝' is Alice's secret to hide H(𝑖), shared to Bob:

In your post secret_p' is the fabricated Bob's secret in order to get another fake H(𝑖) that satisfy the hiding. You explained how such could be done, and this is the point I got confused - once this is done, what are the steps to use the two fabricated fake values to do anything that violates the protocol?

Since now I see how easy it is to add an apostrophe with conflicting meaning then the one used in the protocol, you wouldn't mind me updating the protocol, replacing 𝑝' (the one-time key Alice created for use in this specific Cheque only) with something else? I'm thinking of 𝑐 (for Cheque Key, where 𝑝 was the privacy key intended for π‘–π‘‘π‘’π‘›π‘‘π‘–π‘“π‘–π‘’π‘Ÿ π‘Žπ‘‘π‘‘π‘’π‘ π‘‘π‘Žπ‘‘π‘–π‘œπ‘›) , or 𝑝ₛ, meaning "shared privacy key", or 𝑝ₐ, meaning "Alice's privacy key".

On a second note, I forgot why I hashed 𝑖 in my code - can we define H(𝑖) as 𝑔ⁱ instead of 𝑔ʰ⁽ⁱ⁾ and would that save some gas?

4

Ah, sorry, I was a bit to fast explaining how something causes a problem without actually explaining why it is a problem! The issue is not with the hiding. The code you suggested will definitely hide Bob's secret. The issue is that the hiding is not binding to Bob's mail address (hashed_i). That is, someone would be able to take Bob's attestation and now user their own email to compute hashed_i' and find the corresponding value secret_p' that would be needed to "prove" that they own this attestation. When the attestation is linked to Bob's actual Ethereum address and used to send money (as in the cheque case) this attack would not make much sense. However, there are situations in the ticket use-case where simply proving ownership of the attestation is sufficient, e.g. to prove that you are allowed entry to an event. In that case, simply seeing Bob's attestation is enough to allow someone to prove that they own it and change the email it should be linked to, to any email of their choice. In the converse situation, this attack would also allow an attacker to change the mail of their own attestation and thus pretend to hold an attestation to Bob's email linked to their Ethereum address.

5

We do need to hash the identifier i using a cryptographic hash-function. If we don't then an attacker can construct fake zero-knowledge proofs that he knows s s.t. s'=s^x when trying to cash a cheque. This is because they now have total freedom in picking the base. That is, the hash function ensures that an attacker that wish to fake a zero-knowledge proof can only pick random bases and chose the exponent freely, thus ensuring that they cannot solve the (one-more) discrete log problem efficiently and hence preventing them from doing a fake zero-knowledge proof.

6

Yes! Please feel free to change the notation. To be honest I also sometimes find the prime-notation confusing.

7

The attack by which the adversary who knows Bob's identifier attestation but not the bound key shouldn't be a concern because we can formulate the protocol as such:

  • If Bob has to enter an event venue, or visit a website which requires authentication, he has to provide the zero-knowledge proof as well as signing the proof†, just like the redeem process. Therefore he has to possess not only a secret_p' but also the Ethereum key bound in the identifier attestation.

However, the other attack model: that instead of having Bob's identifier attestation, an adversary has access to Bob's Cheque, as well as the one-time key Alice produced with it.

A real-life example: the adversary is the office manager who collects emails forwarded from colleagues about a magic link such as event ticket, but has no access to those colleagues email INBOX to receive verification code.

Will such an adversary be able to go to the attestor website, claim an attestation with a carefully crafted privacy key 𝑝 and their own email address, then the adversary has an identifier attestation that can redeem the asset to a smart contract?

Back the model where the adversary knows Bob's identifier attestation but not the privacy key & (Ethereum) private key: I failed to see how first calculating the actual (π‘₯,𝑦) point of H(𝑖) makes any difference, since an adversary's capacity depends on having access to Bob's identifier attestation, no matter how the hiding inside it was calculated when Bob got it.

† Ethereum users today are, unfortunately, "used to" signing messages with their Ethereum key when websites asked for it, happily disregarding the separation of authentication key and authorisation key, so we are not offending many by requiring so.

8

If I understand your question correctly, then the answer is yes. The office manager would be able to claim an attestation to their mail address and construct a proof such that they can redeem a cheque that was sent to Bob. Basically if the riddle/public value is computed as g^(hashed_i * secret_p) then there is no binding to hashed_i, there is only hiding. This is the same for the cheque if its riddle is also constructed this way. Simply signing the ZK proof does not fix this issue since the Ethereum key is bound using the attestation, but since the attestation is now not binding, it is possible to prove that the attestation was made to a different mail address than what the attester certified.

9

If the adversary does not know the privacy key used for the cheque, they cannot redeem the cheque. But the key issue is the fact that by computing attestations as s=g^(H(i) * p) instead of s=H(i)^p they will not bind to H(i) and it can be modified to attest to any i by anyone who knows H(i) and p. The binding basically comes from the fact that knowing p does not allow anyone to compute a value p' such that s=H(i')^p' without solving the discrete logarithm problem of s to base H(i'), but in the case of s=g^(H(i) * p) the adversary only has to compute H(i')^-1, which is easy.

10

Okay, thanks for clarifying this! Now it makes much more sense, you want an algorithm to create a hiding with binding. That way we are on the safe side and the office manager Eva won't do harm.

If the above statement is correct, I'll update the part that mentions H(𝑖) in the document (you can do that too if you liike, just fork the document repo and update the file).

I was much involved in the beginning but now I forgot more than half of it, so the document has to be updated even if just for the benefit of the future me.

11

there computePoint() like in java example.

its code for my "createCheque" logic like JAVA example.

12

Overall it looks really good, but I think there are a couple of small issues when I look deeper into the code. I think the code you shared don't reflect the latest update of AttestationCrypto? As far as I can see the latest commit in your JS branch is from before I finished the work on converting to BN256, so it is only logical that it does not reflect the change of curve to BN256 :slight_smile:
Anyway the branch you should compare with in regards to AttestationCrypto is bn256. So just to be clear, the small issues I see are as follows:

  1. It seems that the curve you use is not the same as used in the java code. The prime, curve order and value of parameter B are not correct as they reflect the secp256k1 curve and not BN256.
  2. The latest version of the java code has an extra check in the while-loop. Basically the check is verifying that the point computed is not the point at infinity.
  3. In regards to createAndVerify it looks like the encoding of the riddle is to a bit string where as the java version encodes it as an octet string. Furthermore when I look into the bouncyCastle library it looks like it prepends a byte of value 04 before encoding the point (as far as I can see this is not ASN1 related, so it is not the 04 used to indicate that the following value is an octet string).

@olehhrib Do my comments make sense?

13

I uldated code here. Thank you.

14

Thanks. ComputePoint looks great now! The only other minor thing (which I unfortunately forgot to mention in my last comment, sorry) is that mapToInger and mapToIntegerFromUint8 should now use Keccak 384 instead of Keccak 256. Finally in order to be completely done I think you still need to do the Ticket object implementation (the java reference for this has been merged into the master branch). This can just be based on the code you already have for Cheque, but like I mentioned in the previous comment, I think you still need to prepend a 0x04 to the encoding of the riddle point and encode the riddle point as an octet string instead of a bit string.