4
$\begingroup$

Can somebody lead me to existing literature on making the extraction of plaintext dependent on a valid signature check first? I didn't think it was possible to force signatures to be checked; but this is possible, and I have an implementation of it with RSA.

For background: I have been following the multiple problems with JWT tokens, that manage to turn a common cryptography practice into a very real hazard.

signedData = {plaintext, Sign(Hash(plaintext))}

Until recently, I assumed that you can't force anyone to perform a signature check; and that you should trust the client to defend itself with a correct implementation. But the JWT standard does this:

B64(header) + "." + B64(plaintext) + "." + B64(signature)

The problem with this is that the sort of developers that deal with these tokens will pick the shortest path to getting things done, possibly unaware of bad consequences. So, when they get a JWT token, inevitably:

  • UnB64(split(token, ".")[1]) extract the claims, and ignore the signature, because this works.
  • Allow header to specify trivial-to-forge algorithms like None. That also works.
  • Use the value in claims.issuer to look up a missing trust. This way, you can "perform" the signature check, while defeating the purpose of doing the check; because you dutifully downloaded the trusted public key at the behest of the attacker. This makes untrusted signer errors go away.

So, the way out of this is for the claims to be encrypted. But you need proof that you trust the key id (kid), which may be public only to those allowed to decode the tokens. Instead of a kid value in the header, just make kid the only thing in the header at all.

  • RSA key: (n,d,e), where d is private to signer, n is given to verifiers, and e is well known. Notice that this is an unusual use of RSA, where n is not completely public.
  • You need a witness (random value k) to doing steps correctly to decrypt: E = AESEncrypt(k,claims)
  • Prove that you checksummed the token ciphertext: Hash(E)
  • Proof of a verified signature: V = Xor(k, Hash(E))
  • Signed proof of verified signature (RSA): Sig = (V^d)%n
  • Token is similar to JWT, but incompatible to stop JWT library use: Token = {kid,E,Sig}

Verification:

  • Token is verified by looking up public key via (n,e) = trusts[kid].
  • k = Xor( H(E), (V := (Sig^e)%n) ) Proves that we actually validated signature
  • claims = AESDecrypt(k, E)

This acts as an encrypted token, where the RSA public key is not completely public. It is now impossible to get the claims without verifying the signature first. This fixes the primary misuse of JWT, because bad implementations will only create gibberish. This also resolves the issue of claims that should be secret except to signer and the verifiers.

Real JWT libraries enable every stupid thing imaginable, from automatically using claims.issuer to download public keys for trust over https; to extracting claims without verification, to enabling algorithms that the client is not expecting such as the infamous signature algorithm alg:None.

$\endgroup$

2 Answers 2

3
$\begingroup$

What's asked is met by a “signature scheme giving message recovery” used with “total recovery”, that is with empty “non-recoverable message”†. Then the whole message is embedded in the signature, and remains unintelligible until the better part of the signature verification job has been made (of course it's always possible to skip some check in the signature verification, but at least that's unlikely to happen by accident).

For an RSA-based standard and short messages, there is ISO/IEC 9796-2:2010‡, schemes 2 or 3, with empty “non-recoverable message”. There's an implementation in BouncyCastle as ISO9796d2PSSSigner. If being broken under chosen-messages attack is not to fear, we can consider scheme 1, originally in ISO/IEC 9796-2:1997, commonly used in bank cards and often available in JavaCards. It's described in EMV 4.4 Book 2 section A2.1 with a restriction to byte-aligned messages and keys making it simpler than the standard, but only in “partial recovery” mode which opposes “total recovery”, and for a 20-byte hash (specifically SHA-1).

To remove the message size restriction, we can encrypt the message with a random key (AES-128-CTR will do), and sign with a “signature scheme giving message recovery” the concatenation of the key and ciphertext (in order such that the key is in the recoverable part of the message). ISO/IEC 9796-2 can be used, but in this application I recommend against scheme 1, especially with a hash shorter than 512-bit.

For something (EC)DLP-based and no restriction on message size (because the signature itself uses a cipher much as in the above paragraph), we can use ECPV of ISO/IEC 9796-3:2006‡ with empty “non-recoverable message” MCLR, or ECPVS of ANSI X9.92-1-2009‡ with empty “visible message” V. These standards are based on Pinstov and Vanstone's Postal Revenue Collection in the Digital Age, in proceedings of Financial Cryptography 2000‡, albeit without the per-device key derivation: we skip section 4 and start section 5 with the (public, private) key pair $(Q_A,a)$ obtained as $Q_A=a\,\mathsf{P}$.

Note: Pinstov/Vanstone signature is designed to use redundancy in the recoverable message (e.g. restriction to printable ASCII, or valid JSON) for utmost compactness. If that's not wanted (because the message is arbitrary, or otherwise a robust redundancy-checking method is not available, or we just give up on compactness), we can make some redundancy by appending say 128 bit of zeroes to the recoverable message, and check them on signature verification.

Note: the adoption of Pinstov/Vanstone signature has been low, perhaps because it was patented. But my understanding is that whatever (possibly) relevant IP has expired. At least, anything disclosed in the aforementioned Postal Revenue Collection in the Digital Age paper of FC 2000 is free to use now.


† The “non-recoverable message”, also known as “clear message” or “visible message”, is a fraction of the message that appears in clear along the signature itself in a “signature scheme giving message recovery”. This opposes to the “recoverable message”, that is the part of the message embedded in the signature, and obtained by the verifier only as a byproduct of signature verification.

‡ Paywalled

$\endgroup$
12
  • 1
    $\begingroup$ Can we do a canonical Q/A for signature with message recovery? Standards and practice? $\endgroup$
    – DannyNiu
    Mar 22 at 0:49
  • 1
    $\begingroup$ This is the implementation I created of this idea. It actually is not possible to get the plaintext claims without doing a signature check; in the same way that it's not possible to get the plaintext of encrypted data without a secret key; as I made the decrypt a function of the sig check. In the hands of a web developer (plaintext, Sig(key,plaintext)) is a bonafide hazard. The attacker is the web developer. github.com/rfielding/whiskeyTango $\endgroup$
    – Rob
    Mar 23 at 20:29
  • 1
    $\begingroup$ @Rob: had a look at the scheme, which verification procedure is nicely drawn there, with signature just above. I have reservation on the security of the RSA signature part, which (as far as I understand from that) is textbook RSA signature of a narrow witness of the message. This is subject to the Desmedt and Odlyzko attack. In a nutshell, RSA signature should be on representatives nearly as wide as the public modulus. Independently: RSA private key is not $(n,e,d)$ in practice. $\endgroup$
    – fgrieu
    Mar 24 at 3:23
  • 1
    $\begingroup$ @Rob: yes $e$ and $d$ can be made interchangeable, and the only good reason for small $e$ is performance. But it's not true that almost all of the hazards with RSA in practice are due to using a small $e$. Many attacks still work with random large $e$; and among these the Desmedt and Odlyzko attack that (at least, about) works against your system. For more on why $e=3$ is frowned at, and why that's often for wrong reasons, see this. I made a question about attacking the RSA part of your signature. $\endgroup$
    – fgrieu
    Mar 25 at 14:16
  • 1
    $\begingroup$ @Rob: yes, got that, the code is pretty understandable. My remark "seemingly 512 bits in golang" is about if len(V.Bytes()) > 64 where I think 32 was intended, and is not visible in the verification drawing. I assume that's fixed. My remark about the Desmedt and Odlyzko attack being (borderline) feasible remains. It's about the random-like message representative (your V) being 256-bit rather than (about) as wide as n, which is a condition for security: RSA is (assumed) secure for random message in $[0,n)$, and we can reduce that a little, but not down to $[0,2^{256})$. $\endgroup$
    – fgrieu
    Mar 26 at 7:37
2
$\begingroup$

If you use RSASSA-PSS, then there's a "salt" that must be recovered to verify the signature. I'm not sure if this would be secure, but this salt may be used as key or IV to a symmetric-key cipher to decrypt your data.

Reference: PKCS#1 v2.2.

$\endgroup$
2
  • 1
    $\begingroup$ Yes, but we would need to modify the implementation of RSASSA-PSS to make salt an input and output, and sign the ciphertext. This requires that salt generation is in a step separate from signature production. $\endgroup$
    – fgrieu
    Mar 21 at 9:53
  • $\begingroup$ I'll have to second @fgrieu 's comment - don't break the implementation that's provided to you. $\endgroup$
    – DannyNiu
    Mar 22 at 0:46

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.