Blind signature library in python (or C)
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

Simple library with signing, verifying, encryption and decryption of a 64-byte string of data with blind signatures. It should be using RSA or elliptic curves. If it can use openssl and/or PKCS11 for the actual crypto operations, that would be even better. If the data needs to be longer than 64 bytes for this to work, it can use deterministic padding.

Here is a flowchart of how the library is intended to be used: https://download.bitmessage.org/tmp/Blind%20signature%20flowchart%20(2).svg

Don't worry about how the data is transferred between the parties, that's outside of the scope. Same with creating keys, just assume that we can create keypairs, or simply re-use OpenSSL or PKCS11.

If you prefer C to python, that's ok as well as long as it calls OpenSSL or PKCS11.

The library must be able to be licensed under the MIT license (e.g. in case you're using third party code).

I'm not a crypto expert and it's possible I don't understand how it's supposed to work and what I'm asking for isn't possible. If that's the case, I need to know.

In my opinion this will not be possible. Imagine Epub/Epriv as an envelope; Cpub/Cpriv as a briefcase; and D as a secret document. Now the second procedure in the flowchart is like putting the document in the envelope. The third procedure (the one in Certifier lane) is putting the envelope in the briefcase. Then for the next procedure you want to take the document out of the envelope while it is still inside the briefcase. You can see how this is hard to achieve. The briefcase will have to have its own mechanics to be able to know how to open the envelope. No such briefcase (ie encryption algorithm) exists to my knowledge.
chesedo 19 days ago
The way I understand it, blind signatures use homomorphic encryption to achieve the ability to perform operations on ciphertext which are reflected on the plaintext. Blind signatures were originally invented by David Chaum in 1983. There are many academic papers which analyse this or that way of using them. Unfortunately I don't have time to read them and try to implement it myself. Here is an example implementation for python, but I don't know how well it works: https://github.com/ashuanindian/Blind-Signature
PeterSurda 19 days ago
Interesting... I learned something new!
chesedo 19 days ago
awarded to CyteBode

Crowdsource coding tasks.

1 Solution

Winning solution

The way I understand it, the algorithm presented in your flowchart can't work.

Let:
         e: The certifier's public key exponent (encryption)
         d: The certifier's private key exponent (decryption)
         n: The product of e and d
   epsilon: The creator's ephemeral public key exponent
     delta: The creator's ephemeral private key exponent
        nu: The product of epsilon and delta

Working out the math, it might seem like the algorithm would work:

   enc = m^epsilon (mod nu)             (encryption: c = m^e (mod n))
encsig = (m^epsilon)^d (mod n)          (signing: s = m^d (mod n))
   sig = ((m^epsilon)^d)^delta (mod nu) (decryption: m = c^d (mod n))
       = ((m^d)^epsilon)^delta (mod nu) (commutativity)
       = m^d (mod n)                    ((m^e)^d = m (mod n))
                                        (signing: s = m^d (mod n))

However, n != nu, as (e, d) and (epsilon, delta) are different. Therefore, the properties don't hold.

The way blind signing is normally done (as shown here) is to use a random number to compute m' = m*r^e (mod n) using the certifier's public key. Then the certifier signs that which gives s' = (m')^d (mod n) = (m*r^e)^d (mod n). For unblinding, s' is divided by the same random number: s = s' / r (mod n) = (m*r^e)^d / r (mod n). As (r^e)^d = r (mod n), we get s = m^d (mod n), which is the signature we want.

Here is some code doing blind signing this way: https://stackoverflow.com/a/33982599. I've tried it and it works. I've adapted the code to follow the certifier/creator/validator structure, but I don't know if it would be of any use to you since it uses pycrypto instead of OpenSSL.

ECC Blind signature

I found a paper showing a suitable ECC blind signature schema. It's a fair bit more complicated than your flowchart.

I suppose you ultimately want this to end up in PyBitmessage, so I went with pyelliptic as a dependency, which PyBitmessagealready uses for ECC.

First, since pyelliptic only includes the OpenSSL functions it uses, pyelleptic/openssl.py needs to be modified to include new functions:

print("A bit of Python just to help the syntax highlighter")

# That goes in _OpenSSL's __init__ method
self.BN_CTX_new = self._lib.BN_CTX_new
self.BN_CTX_new.restype = ctypes.c_void_p
self.BN_CTX_new.argtypes = []

self.BN_dup = self._lib.BN_dup
self.BN_dup.restype = ctypes.c_void_p
self.BN_dup.argtypes = [ctypes.c_void_p]

self.BN_rand = self._lib.BN_rand
self.BN_rand.restype = ctypes.c_int
self.BN_rand.argtypes = [ctypes.c_void_p, ctypes.c_int, ctypes.c_int]

self.BN_set_word = self._lib.BN_set_word
self.BN_set_word.restype = ctypes.c_int
self.BN_set_word.argtypes = [ctypes.c_void_p, ctypes.c_ulong]

self.BN_mul = self._lib.BN_mul
self.BN_mul.restype = ctypes.c_int
self.BN_mul.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

self.BN_mod_add = self._lib.BN_mod_add
self.BN_mod_add.restype = ctypes.c_int
self.BN_mod_add.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

self.BN_mod_inverse = self._lib.BN_mod_inverse
self.BN_mod_inverse.restype = ctypes.c_void_p
self.BN_mod_inverse.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

self.BN_mod_mul = self._lib.BN_mod_mul
self.BN_mod_mul.restype = ctypes.c_int
self.BN_mod_mul.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

self.BN_lshift = self._lib.BN_lshift
self.BN_lshift.restype = ctypes.c_int
self.BN_lshift.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_int]

self.BN_sub_word = self._lib.BN_sub_word
self.BN_sub_word.restype = ctypes.c_int
self.BN_sub_word.argtypes = [ctypes.c_void_p, ctypes.c_ulong]

self.BN_cmp = self._lib.BN_cmp
self.BN_cmp.restype = ctypes.c_int
self.BN_cmp.argtypes = [ctypes.c_void_p, ctypes.c_void_p]

self.BN_bn2dec = self._lib.BN_bn2dec
self.BN_bn2dec.restype = ctypes.c_char_p
self.BN_bn2dec.argtypes = [ctypes.c_void_p]

self.BN_CTX_free = self._lib.BN_CTX_free
self.BN_CTX_free.argtypes = [ctypes.c_void_p]

self.EC_GROUP_new_by_curve_name = self._lib.EC_GROUP_new_by_curve_name
self.EC_GROUP_new_by_curve_name.restype = ctypes.c_void_p
self.EC_GROUP_new_by_curve_name.argtypes = [ctypes.c_int]

self.EC_GROUP_get_order = self._lib.EC_GROUP_get_order
self.EC_GROUP_get_order.restype = ctypes.c_int
self.EC_GROUP_get_order.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

self.EC_GROUP_get_cofactor = self._lib.EC_GROUP_get_cofactor
self.EC_GROUP_get_cofactor.restype = ctypes.c_int
self.EC_GROUP_get_cofactor.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

self.EC_GROUP_get0_generator = self._lib.EC_GROUP_get0_generator
self.EC_GROUP_get0_generator.restype = ctypes.c_void_p
self.EC_GROUP_get0_generator.argtypes = [ctypes.c_void_p]

self.EC_POINT_copy = self._lib.EC_POINT_copy
self.EC_POINT_copy.restype = ctypes.c_int
self.EC_POINT_copy.argtypes = [ctypes.c_void_p, ctypes.c_void_p]

self.EC_POINT_add = self._lib.EC_POINT_add
self.EC_POINT_add.restype = ctypes.c_int
self.EC_POINT_add.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

self.EC_POINT_cmp = self._lib.EC_POINT_cmp
self.EC_POINT_cmp.restype = ctypes.c_int
self.EC_POINT_cmp.argtypes = [ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p, ctypes.c_void_p]

self.EC_POINT_set_to_infinity = self._lib.EC_POINT_set_to_infinity
self.EC_POINT_set_to_infinity.restype = ctypes.c_int
self.EC_POINT_set_to_infinity.argtypes = [ctypes.c_void_p, ctypes.c_void_p]

Next, here's a crude demo showing the algorithm in action:

import os

from pyelliptic.openssl import OpenSSL


def ec_get_random(group, ctx):
    order = OpenSSL.BN_new()
    OpenSSL.EC_GROUP_get_order(group, order, ctx)

    OpenSSL.BN_rand(order, OpenSSL.BN_num_bits(order), 0, 0)
    return order


def ec_invert(group, a, ctx):
    order = OpenSSL.BN_new()
    OpenSSL.EC_GROUP_get_order(group, order, ctx)
    m = OpenSSL.BN_num_bits(order)

    inverse = OpenSSL.BN_mod_inverse(0, a, order, ctx)
    return inverse


def ec_gen_keypair(group, ctx):
    d = ec_get_random(group, ctx)

    Q = OpenSSL.EC_POINT_new(group)
    OpenSSL.EC_POINT_mul(group, Q, d, 0, 0, 0)

    return (d, Q)


if __name__ == "__main__":
    """ (1) Intialization """
    # Field: F(2^283)
    group = OpenSSL.EC_GROUP_new_by_curve_name(OpenSSL.get_curve("sect283r1"))

    ctx = OpenSSL.BN_CTX_new()

    # Order n
    n = OpenSSL.BN_new()
    OpenSSL.EC_GROUP_get_order(group, n, ctx)

    # Identity O
    O = OpenSSL.EC_POINT_new(group)
    OpenSSL.EC_POINT_set_to_infinity(group, O)

    # Generator G
    G = OpenSSL.EC_GROUP_get0_generator(group)

    # Certifier's keypair
    keypair = ec_gen_keypair(group, ctx)
    public = (group, G, n)

    """ (2) Request """
    # Signer: Random integer k
    k = ec_get_random(group, ctx)

    # R = kG
    R = OpenSSL.EC_POINT_new(group)
    OpenSSL.EC_POINT_mul(group, R, k, 0, 0, 0)

    # Requester: 3 random blinding factors
    F = OpenSSL.EC_POINT_new(group)
    OpenSSL.EC_POINT_set_to_infinity(group, F)
    temp = OpenSSL.EC_POINT_new(group)
    Q = keypair[1]
    abinv = OpenSSL.BN_new()
    # F != O
    while OpenSSL.EC_POINT_cmp(group, F, O, ctx) == 0:
        a = ec_get_random(group, ctx)
        b = ec_get_random(group, ctx)
        c = ec_get_random(group, ctx)

        # F = b^-1 * R...
        binv = ec_invert(group, b, ctx)
        OpenSSL.EC_POINT_mul(group, temp, 0, R, binv, 0)
        OpenSSL.EC_POINT_copy(F, temp)

        # ... + a*b^-1 * Q...
        OpenSSL.BN_mul(abinv, a, binv, ctx)
        OpenSSL.EC_POINT_mul(group, temp, 0, Q, abinv, 0)
        OpenSSL.EC_POINT_add(group, F, F, temp, 0)

        # ... + c*G
        OpenSSL.EC_POINT_mul(group, temp, 0, G, c, 0)
        OpenSSL.EC_POINT_add(group, F, F, temp, 0)

    # F = (x0, y0)
    x0 = OpenSSL.BN_new()
    y0 = OpenSSL.BN_new()
    OpenSSL.EC_POINT_get_affine_coordinates_GFp(group, F, x0, y0, ctx)
    r = x0

    # Requester: Blinding (m' = br(m) + a)
    msg = os.urandom(64)
    m = OpenSSL.BN_new()
    OpenSSL.BN_bin2bn(msg, len(msg), m)

    m_ = OpenSSL.BN_new()
    OpenSSL.BN_mod_mul(m_, b, r, n, ctx)
    OpenSSL.BN_mod_mul(m_, m_, m, n, ctx)
    OpenSSL.BN_mod_add(m_, m_, a, n, ctx)

    """ (3) Signature generation """
    s_ = OpenSSL.BN_new()
    OpenSSL.BN_mod_mul(s_, keypair[0], m_, n, ctx)
    OpenSSL.BN_mod_add(s_, s_, k, n, ctx)

    """ (4) Extraction """
    s = OpenSSL.BN_new()
    OpenSSL.BN_mod_mul(s, binv, s_, n, ctx)
    OpenSSL.BN_mod_add(s, s, c, n, ctx)

    signature = (s, F)

    """ (5) Verification """
    lhs = OpenSSL.EC_POINT_new(group)
    rhs = OpenSSL.EC_POINT_new(group)

    OpenSSL.EC_POINT_mul(group, lhs, s, 0, 0, 0)

    OpenSSL.EC_POINT_mul(group, rhs, 0, Q, m, 0)
    OpenSSL.EC_POINT_mul(group, rhs, 0, rhs, r, 0)
    OpenSSL.EC_POINT_add(group, rhs, rhs, F, ctx)

    assert OpenSSL.EC_POINT_cmp(group, lhs, rhs, ctx) == 0
    print("OK!")

Note that nothing is being freed (as it should be) and there is no error handling, so the code shouldn't be used for production at all.

I have yet to turn this into a more usable library. This shouldn't take too long, but adding the missing functions and writing the demo was already pretty involving.

I also need to make sure that it's really working properly and that I'm doing everything right (I think I'm confusing the order n with q = 2^m). For now, I know that the signature passes verification with the same message, and that it expectedly fails when the message is different.

Let me know if I'm on the right track.

Edit 1&2: Typos.

Edit 3: Added ECC blind signature.

Edit 4: Fixed missing ctx argument in declarations of BN_mul and BN_mod_mul. Fixed the point comparison (F == O) being made with BN_cmp instead of EC_POINT_cmp. Made the calls to EC_POINT_mul use a null ctx argument.

This explains what I've been missing (the usage of certifier's public key in the first phase). I think that the flowchart can be appropriately modified, the Creator does know the Certifiers' public key. The code you posted is a good start, it works for me too, however I'd really prefer it used elliptic curves and openssl (if possible, I don't know for sure openssl supports this).
PeterSurda 19 days ago
You're definitly on the right track. Yes, ideally I want to extend pyelliptic like you do. One minor note, pyelliptic has been abandoned, PyBitmessage maintains its own fork, mainly for adding support for OpenSSL 1.1.0 which changed some APIs. I briefly looked at the functions you used, and it looks like there was no change in them between 1.0.2 and 1.1.0, so it should be ok. I tried the code you wrote, and it's segfaulting at OpenSSL.EC_POINT_mul(group, Q, d, 0, 0, ctx) I'm using python 2.7.15 and openssl 1.1.1a. Any ideas?
PeterSurda 18 days ago
I was using OpenSSL 1.0.2q for testing, but there were a few bugs in my code that prevented it to work properly with a newer version. I have fixed them (see the last edit) and it's actually funny that it even worked at all! I have tested it with 1.1.1 and it's now working with no segfault for me.
CyteBode 18 days ago
I just noticed: the definition of EC_POINT_mul (which was already present in openssl.py) is missing the ctx argument as well (it needs a sixth ctypes.c_void_p argument). When added, the calls to EC_POINT_mul work properly with a non-null ctx. EC_POINT_add doesn't need a null ctx either.
CyteBode 18 days ago
This probably is what I want. Structure-wise it's minimalistic and straightforward. It does print "OK!", even if I change the curve. I just need time to look at the math, will try to do it today. If it's ok then I'll approve. Do I understand correctly that in order to verify, you have to transmit m(essage), s(ignature). What about r and F, are they shared too? And Q is the certifier's public key (which in my framework will be pre-shared)? Or maybe I should just read the paper you referenced. In addition to that, if you're interested on working on other tasks for Bitmessage , send me an email and we can discuss.
PeterSurda 18 days ago
Section 4 of the paper has all the info that you need, and I wrote the code to follow the math as closely as I could. You need both the message and its signature to verify it (a signature on its own is meaningless), and it's verified using the verifier's public key Q. F is the point (x0, y0) and r = x0. The signature itself is (s, F) so r and F are indeed shared (r being part of F and F being part of the signature). For the blind signature itself, the requester needs R from the signer, which it generates from a random k for every signature. It also needs to keep that value k to sign with.
CyteBode 18 days ago
So I compared the math in the paper with the code, it seems to be the same. What was confusing me was that I didn't realise that the process needs one extra roundtrip compared to my diagram. This may actually end up being better for privacy, as I can introduce an extra party which will create k and send it to the signer and R to the requester. The extra party can verify that the requester is authorised to obtain the signature, and the signer doesn't have to know who the requester is.
PeterSurda 17 days ago
Thanks for awarding me the bounty! Right, the flowchart in the paper deceivingly looked a lot like yours, but that's because it doesn't show the first step of distributing Q to both the requester and the verifier, as it's treated as a given. I haven't read the paper in whole, but from what I understand, the proxying with the (k, R) ephemeral key is so the signer can avoid directly reusing its private key over and over again. Do you still need me to refactor the code into a more reusable library? If so, what kind of API do you want?
CyteBode 17 days ago
At the moment I don't need more code, I just wanted to make sure it works so that I can continue working on other things. It will take a while before I need to merge it. But as I said, if you would like to do more crypto work on PyBitmessage, you can email me at peter@bitmessage.org, For example encrypting the config file, forward secrecy, using PKCS11 for key storage and things like that.
PeterSurda 17 days ago