3
$\begingroup$

Continued from Is there a flaw in this ECC blind signature scheme?

The problem

I needed a partially blind signature scheme for one of my projects, but couldn't find one on the internet, so I've made one (I think).

Is there anyone who can verify my results

Actors

  • Alice (signer, i.e. bank)
  • Bob (requester, i.e. payer)
  • Bill (Verifier, i.e payee)

All actors agree on elliptic curve parameters:

Curve: y^2 = x^3 + a*x + b mod p
Base point: P
Order of base point: n

Alice generates his private key by choosing random value x in [1, n-1] range, then she computes and publishes Q = x*P

The algorithm

Alice holds record for Bob's and Bill's account balances, Bob want's to make a payment to Bill. For that purpose:

  1. Bob generates a token message M = "This is 5 dollar Serial No. 111222333"
  2. Bob generates public info message Z = "Nominal: 5, Currency: USD, Expiry date: 2018-01-01 12:00:00Z",
  3. Bob hashes his token message which results with m = hash(M)
  4. Bob hashes his public info message z = hash(Z)
  5. Bob generates random blinding factor v = random()
  6. Bob blinds his token message u = (m - v) mod n
  7. Bob sends (u, Z) to Alice
  8. Alice by looking into Z = "Nominal: 5, Currency: USD, Expiry date: 2018-01-01 12:00:00Z" sees that Bob want to charge 5 USD from his account
  9. Alice charges 5 USD from Bob's account and blindly signs u by generating pair (s', R')
    1. For that purpose Alice generates random value r = random() that will be used for protecting her private key x
    2. Then Alice computes s' = (x - r + u + hash(Z)) mod n = (x - r + u + z) mod n
    3. And R' = r * P
  10. Alice sends the resulting (s', R') pair to Bob
  11. By receiving (s', R') Bob unblinds the message into (s, R), this is done according to following steps:
    1. Bob generates random unblinding factor w = random()
    2. Bob then computes s = (s' + w - m) mod n
    3. Bob then computes R = R' + (m - w - v)*P
  12. Bob then pays for services from Bill by sending him tuple (s, R, Z, M)
  13. By receiving Bob's tuple (s, R, Z, M) Bill validates:

    1. Token message M = "This is 5 dollar Serial No. 111222333"
    2. Public info Z = "Nominal: 5, Currency: USD, Expiry date: 2018-01-01 12:00:00Z"
    3. The signature (s, R) by checking equation s*P - Q + R = z*P + m*P:
    4. Since s = s' + w - m then s is also equal to x - r + v + z + w
    5. Since R = R' + (m - w - v)P then R is also equal to r*P + (m - w - v)*P which in turn is equal to r*P + m*P - w*P - v*P
    6. Then the initial equation s*P - Q + R = z*P + m*P yields to:

      (x - r + v + z + w)*P - Q + (r*P + m*P - w*P - v*P) = z*P + m*P

      which in turn yields to:

      x*P - r*P + v*P + z*P + w*P - Q + r*P + m*P - w*P - v*P = z*P + m*P

      by applying simplification we get that:

      z*P + m*P = z*P + m*P

  14. After performing validation checks Bill asks Alice to add 5 USD to his account by sending her the tuple he received from Bob (s, R, Z, M)

  15. When Alice receives (s, R, Z, M)

    1. She validates Z = "Nominal: 5, Currency: USD, Expiry date: 2018-01-01 12:00:00Z"
    2. She validates M = "This is 5 dollar Serial No. 111222333"
    3. She adds (111222333, 2018-01-01 12:00:00Z) to her database of expired tokens
    4. The token will be deleted after 2018-01-01 12:00:00Z preventing the database to grow indefinitely

Alice is able to verify her own signature (s, R, Z, M) by repeating steps made by Bill though she is not able to track who made a payment to Bill. It's true because even if Alice has recorded the s' component in her database during signature phase, she will not be able to match it because during repayment phase she will receive (s, R) instead of (s', R') and so by subtracting recorded s' from s she will get:

s - s' = ((x - r + v + z + w) - (x - r + v + m + z) + m + z) mod n =
       = (x - r + v + z + w - x + r - v - m - z + m + z) mod n = 
       = w mod n

and there's no way for Alice to discover w

Here is another example with real numbers: https://dl.dropboxusercontent.com/u/51743054/PartiallyBlindSignatureExample.pdf

P.S. The scheme provided in the following paper seem like has a flaw in it (during signature phase, a signer may embed requesters identity data into h(z) which may be recovered during verification phase and so requester's identity may be disclosed by the verifier, if signer and verifier share common database):

http://ijns.femto.com.tw/contents/ijns-v14-n6/ijns-2012-v14-n6-p316-319.pdf

I've taken that paper as a base work and fixed (I think) the problems that were in it, now it shouldn't leek requester anonymity.

$\endgroup$
6
  • $\begingroup$ I'd consider using RSA based blind signatures. It's simple, robust and supports tons of additional features. The main downsides are the lower performance and larger signatures. $\endgroup$ May 7, 2014 at 8:25
  • $\begingroup$ @CodesInChaos yes, but the OP is looking for a partially blind signature scheme - and no secure RSA based scheme is known (AFIAK). $\endgroup$
    – DrLecter
    May 7, 2014 at 9:08
  • $\begingroup$ I've changed my question, added description to an algorithm so it should be more clear now how the things are working $\endgroup$
    – Lu4
    May 7, 2014 at 10:51
  • $\begingroup$ @DrLecter "no secure RSA based scheme is known"? You mean Chaum's blind signature is not secure? $\endgroup$
    – Lu4
    May 8, 2014 at 9:25
  • $\begingroup$ @Lu4 no, Chaums one is a secure blind signature scheme but not a partially blind scheme (and if you want to make it partially blind I am only aware of approaches that are insecure). $\endgroup$
    – DrLecter
    May 8, 2014 at 9:27

1 Answer 1

6
$\begingroup$

Designing such signature schemes from scratch without having strong experience is very likely to fail and very dangerous (see the tons of bad papers out there being accepted to "dubious" conferences and journals).

Your proposed scheme

Your verification relation is to check if: $sP - Q + R \stackrel{?}{=} zP + mP$ where $Q$ is the public key of the signer and lets call $hash$ simply $h$.

I just took a quick look and you have the following problem (observe that you can freely choose $s$ and $R$):

Set $R:=Q$, choose any $M$ and $Z$ of your choice, then set $s:= h(Z)+h(M) \bmod n$ and the verification relation holds. Thus, you can forge a signature for arbitrary $M$ and $Z$ of your choice.

Ok, now you could say: "Lets introduce a check if $Q=R$ and whether $s$ is not of the form $h(Z)+h(M) \bmod n$ to avoid this problem".

But you can arbitrarily "blind" $s$ and $R$ set $R=Q-aP$ for an arbitrary $a\in \mathbb{Z_n}$ and then set $s:= h(Z)+h(M)+a \bmod n$. Note that your verification relation requires that:

$$sP - Q + R = zP + mP$$

Now lets plug in

$$(h(Z)+h(M)+a)P - Q + (Q-aP) = h(Z)P+h(M)P=mP+zP$$

which is a valid forgery and also totally breaks your scheme. Now you may introduce an additional check that $s$ and $R$ are not blinded that way. But I am quite sure (since I just took a quick look) that you will find more issues (this is still a key only attack and to achieve unforgeability we speak of security against chosen message attacks).

I just want to give you the advice that designing signature schemes (irrespecitve whether they are standard signature schemes, or blind or partially blind or what else) is an art and in your situation (for a project) I think its the best advice to simply rely on established schemes (see at the bottom of the answer). If you still want to desgin signature schemes study the required security properties at first and then think about how you could meet them (and you should also provide a proof that these properties hold).

The approach in your linked paper

The authors of the paper you have linked to seem to have no idea how the accepted security model for blind signatures and in particular the blindness property is defined.

Basically blindness requires that a malicious signer who is allowed to specify two messages $(M_0,M_1)$ and executing the signing process for both messages with a honest receiver is not able to decide in which order the signing processes have been executed.

Now, in your linked paper, the signer can trivially do so for the two messages: Namely, if the signer receives a candidate "blinded message" $m_bQ$ (where $b$ is either 0 or 1, he does not know, and $m_b=H(M_b)$), then the signer simply checks if $H(M_0)Q$ equals the received $m_bQ$. If this is the case he signs $M_0$ in this process and $M_1$ otherwise. Consequently, the scheme is not providing the blindness property.

Actually, they seem to more likely want to build a partially blind signature scheme, but the scheme will also not satisfy partial blindness (for the same reason as above).

I did not even look at the unforgeability (non-forgeability as they call it) of the scheme as the above is sufficient to throw away the paper. But as their models seem very handcrafted and the "proofs" are not convincing, I guess it can be broken w.r.t. this property as well.

Existing partially blind signature schemes

A well accepted and quite standard approach to partially blind signatures is the one in this paper by Abe and Okamoto (and this can also be implemented on elliptic curves). This one (more of theoretical interest) and this one are also provably secure (in the standard model in contrast to the first) but rely on pairing friendly elliptic curves. So maybe the easiest one to implement is the first one.

$\endgroup$
9
  • $\begingroup$ Nice answer, no luck with my project, anyway now I understand how this ECC mantra works and more than that now I have the literature describing the process. However I may still wanna try fixing the forgery pattern you've found, I think it will take some time for me to work-through the papers you've proposed. Unfortunately as you see there is huge amount of low level literature on the subject flying around on the internet, and it takes time to distinguish good one from bad one, and if I'd were to use the proposed scheme without asking it wouldn't work in the end, so thank you for your time. $\endgroup$
    – Lu4
    May 7, 2014 at 13:36
  • $\begingroup$ I would appreciate if you add more references later $\endgroup$
    – Lu4
    May 7, 2014 at 13:40
  • $\begingroup$ @Lu4 I added two more references. There are not so many out there that are proven to be secure. I'd go with the one due to Abe and Okamote as it should not be too hard to implement for your project. $\endgroup$
    – DrLecter
    May 7, 2014 at 14:17
  • $\begingroup$ Where you have h(Z)+h(Z), one Z should be M. $\endgroup$ May 7, 2014 at 19:43
  • 1
    $\begingroup$ @Lu4 If you work in elliptic curves you can directly work in the prime order n group. If you work in $Z_p^*$ there are various ways to generate p and q. Surely can q divide p−1 (p-1 is not prime, p is). Just ask a new question. But I am quite sure someone else has already asked this before here. $\endgroup$
    – DrLecter
    May 8, 2014 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.