Issues found

Before starting, I would like to say that so far no exploit was found regarding these issues (but feel invited to participate in the discussion about how to verify or exploit it). Let's go to the facts.

Stealth-addresses not in the main subgroup (Fungibility issue)

I have been verifying the blockchain using the LibSodium library, which is a library "safer" than Monero as it only allows multiplications inside the prime subgroup, in order to check ring signatures and verify if the key_images belong to the prime subgroup, and noticed that there are many points (stealth_addresses) that actually don't belong to the prime subgroup. I have finished scanning (up top height 2651355) and the full list can be found here.

So far, for the first 2.5 million blocks, there are 8931 transactions with 16 different stealth addresses that don't belong to the prime subgroup. Most of them come from version 1 blocks and they are basically the point P=9b2e4c0281c0b02e7c53291a94d1d0cbff8883f8024f5142ee494ffbbd088071, which is the genesis point copied from Bytecoin. The points (Stealth addresses) are:

  • b10ba13e303cbe9abf7d5d44f1d417727abcc14903a74e071abd652ce1bf76dd
  • 52d128bc9913d5ee8b702c37609917c2357b2f587e5de5622348a3acd718e5d6
  • fccffc95974651a33178b0aa235f058c3bc84769aa77939a53c1e936a991152d
  • e6f4ef5858e51bc046b195b41df7720a5583fbc92a6bff15d8216ad30d9a6949
  • 7c09e068d605f7debf5271f97901d122cf3430649ac25328deb91e8498972357
  • c574420256922b0783196e42c98156814e61d9ffa87c1262089be1d42e5f0d27
  • bc14c62db31ca6441c469443452fb609f3d8153d9855d7b4ee418fe63c5e35bc
  • b8ed916c56b3a99c9cdf22c7be7ec4e85587e5d40bc46bf6995313c288ad841e
  • 9b2e4c0281c0b02e7c53291a94d1d0cbff8883f8024f5142ee494ffbbd088071
  • 1b452b4ac6c6419e06181f8c9f0734bd5bb132d8b75b44bbcd07dd8f553acba6
  • 3e8cd0f1cd3035c5e5b7b78d7aa35c0f45d395cb39b69df2a71d166a938efc15
  • 8e7b4a8916c466874788030bb3e93db765016bee09313690412f910e045ec3ea
  • 2a74a3c4c36d32e95633d44ba9a7b8188297b2ac91afecab826b86fabaa70916
  • 4844a2fec06bc897540533f500438d2c3d7a1f11b8715b28a9611de2b2ca73ae
  • 6910bdf7beeae858bb3d3ded00184ed56ab62f8b13948a1bd9a9f63036e876f4
  • 2757dd54027e93c917251de2cc6777f7a3fa484f5b244ab54bf8783e7da80c36}

NOTICE THAT I DID NOT FIND ANY KEY_IMAGE POINT THAT IS OUTSIDE THE MONERO PRIME SUBGROUP. WHICH WOULD MEAN (IF I HAD FOUND) THAT SOMEONE COULD HAVE EXPLOITED IT FOR A DOUBLE-SPENDING.

Severity: It is not severe as it cannot be straight forward exploited as Monero nodes checks if the key_images belong to the prime subgroup.

This issue has other implications too:

  • Prevents other implementations of wallets and nodes that use the LibSodium library. (A block/transaction containing a stealth-address or a ring-member outside the prime subgroup would be accepted in the Monero software but would raise an error on wallets using the LibSodium or Ristretto library)
  • Damages fungibility. Someone looking at the ring-members could tell that a member does not belong to the prime-subgroup and consequently deduce that this member is or is not the owner of the transaction if he has more information about how it was generated (with the last Monero software or not).
  • This is a fungibility issue as it is pretty easy to identify the transactions where this is happening. The full discussion is here.

    Wrong signatures in the blockchain (Malleability issue)

    While scanning the blockchain with my reliable Python tools, as I am using the LibSodium library for all the crypto operations, I found a mismatch between a signature and its expected value. So basically, a wrong signature. At the time I was not sure if it was a bug in my code or Monero's code. After analyzing carefully every multiplication I found out that Monero was performing a wrong operation. More precisely, there is a function called addKeys2(res,a,b,B) that does res = aG+bB and the result of this function is wrong for certain non reduced scalars. You can check by yourself running the snippet below in C++ using the Monero libraries:

    rct::key P1,bbee,bbs0,b2,res;
    rct::key C,D,E1,E2,P1bbee,Base;
    
    epee::string_tools::hex_to_pod("1a7112a70bf953ce7061693f145add80fea7cfaf50456e1440622cc7a986e2a1", P1);
    epee::string_tools::hex_to_pod("cb2be144948166d0a9edb831ea586da0c376efa217871505ad77f6ff80f203f8", bbs0);
    epee::string_tools::hex_to_pod("e8c079d208b352a71abd36a5deb45c67c276efa217871505ad77f6ff80f20308", b2);
    epee::string_tools::hex_to_pod("a29635109c80c54623a8a63e412daec9bc4646fdad9ac5db006d7c541b645302", bbee);
    
    
    C = scalarmultBase(bbs0);
    D = scalarmultBase(b2);
    
    
    scalarmultKey(P1bbee,P1,bbee);
    addKeys(E1, C, P1bbee);
    addKeys(E2, D, P1bbee);
    
    
    std::cout << "Result of scakarmultBase C: " << std::endl;
    std::cout << epee::string_tools::pod_to_hex(C) << std::endl;
    
    std::cout << "Result of scakarmultBase D: " << std::endl;
    std::cout << epee::string_tools::pod_to_hex(D) << std::endl;
    
    std::cout << "Result of C + P1: " << std::endl;
    std::cout << epee::string_tools::pod_to_hex(E1) << std::endl;
    
    std::cout << "Result of D + P1: " << std::endl;
    std::cout << epee::string_tools::pod_to_hex(E2) << std::endl;
    
    addKeys2(res, b2, bbee, P1);
    std::cout << "Result of multiplication reduced: " << std::endl;
    std::cout << epee::string_tools::pod_to_hex(res) << std::endl;
    
    addKeys2(res, bbs0, bbee, P1);
    std::cout << "Result of multiplication not reduced: " << std::endl;
    std::cout << epee::string_tools::pod_to_hex(res) << std::endl;
    
    

    And the result is the following:

    Result of scakarmultBase C: 
    4014ab9200745ab76fab92fb92c6ba162372c8449b8cbd5485f4676c2d823a0d
    Result of scakarmultBase D: 
    4014ab9200745ab76fab92fb92c6ba162372c8449b8cbd5485f4676c2d823a0d
    Result of C + P1: 
    101713c9e5f1184343eaf50c6626bb4fddd90a9886a99ff337d101ed2dd62433
    Result of D + P1: 
    101713c9e5f1184343eaf50c6626bb4fddd90a9886a99ff337d101ed2dd62433
    Result of multiplication reduced: 
    101713c9e5f1184343eaf50c6626bb4fddd90a9886a99ff337d101ed2dd62433
    Result of multiplication not reduced: 
    97a2c482e50176969a66683609c4aea719b5c3ab4535ae4b33b01307c4fbf1a6
    

    Which should be the same no matter if reduced or not! What is happening is that Monero is interpreting a, in the equation res = aG+bB, as another scalar different from its reduced form. Generating, therefore, a wrong signature and it also accepts (verify as correct) a wrong signature as it doing the same mistake to interpret these different scalars.

    Why that is happening?

    So far, the best explanation is because of a pre-requisite in the function ge_double_scalarmult_base_vartime which requires a[31]<=127.

    How bad is that?

    It is clear now that Monero has stored wrong rangeproofs signatures (Borromean signatures) that do not correspond to the stored value in the blockchain to be verified, an easy way to see it is by performing res = aG+bB using two different methods as shown above. So basically you stored 1 and 1 and asks to the blockchain to verify if the inputs adds to 2. Monero is doing 1+2 saying that it is equal to 3 and accepting the proof. It is not so bad though as it is also making a mistake in interpreting these scalars so instead of that being exploited it is a kind of malleability issue.

    Implications

    A full research is being conducted by me (and now I invite everyone else too) to answer the extend and possible vulnerabilities coming from this mistake. As I have proved, the function addKeys2 is wrong for certain inputs and therefore it should be replaced or we should make sure that the inputs obey certain conditions, like being reduced (get the mod of the order of the curve). After a fruitful discussion with Koe, Moneromooo and Luigi, which I am very thankful for their replies, I believe it will be done soon but we are not really concerned as all CLSAG and Bulletproofs functions already make sure of that. There are other minor functions that don't yet though.

    So far I have only logged three transactions that presents this behaviour but I have also neglected some as I was thinking that my code was buggy :p I'm pretty sure that there are more than three that presents wrong Borromean signatures in the blockchain, which does not directly reads as inflation has happened.

    The funky transactions are:

    • e4b7982b081a17892525f1b1d3011ec06a0820cbf451d3a64f8ea998104a753c
    • d5d725e7a76dab7e2ca97d941403936a0fbf5e8874e9ef3becd973e4598a8cb1
    • 0647d386365f6bfd312b0fbe966f5c85f19159ccf9003af8387f332451e6c94c

    What can we do?

    I am still digging deeper into this issue and looking for possible vulnerabilities, which I did not find any so far. It is still an open issue for me and I cannot fully explain all the implications and reasons for this to be happening as I do not fully understand all the lines that the C libraries are doing (yet :p). Meanwhile, I suggested to double check the inputs of the functions using addKeys2. Specially genC, which seems to me a vulnerable point but not exploitable though as it would be pretty hard to find any relation between G and H.

    If you try to exploit it alone at home, please share your results like I am doing so we can achieve a consensus faster :)

    The full discussion is here.

    The most updated report is here.