0

I need to design a scheme, where access to an offline System is granted based on some kind of information/proof of knowledge, provided by a separete system, Prover system.

I'm in position where I can put any information on both Systems.

The perfect-world scenario goes like this

  1. User of an Offline System (S) wants to access protected resource
  2. S presents the user some challenge string
  3. User retypes the challenge in a Prover (P) (which has its own capabilities to check the user is authorized to do so)
  4. The Prover computes and presents the response to the user
  5. User retypes the response to System
  6. System verifies the response and grants access

The above scenario is time-constrained: the System will allow for time between performing 1. and 6. to be not greater than 2-5 minutes.

The additional requirement is protection against replay attacks against offline System.

Also I'd like to avoid keeping static shared secret on the offline System (so TOTP/HOTP is a no-go for me).

The biggest challenge for me is the size of strings the user has to retype in 3. and 6. It should fit within like 20 characters each, or assuming Base64 encoding, around 128 bits.

I'd go with Prover's public key installed on the System, a random string in 3. and a Prover's signature in 6, but from what I saw the size of the signature is prohibitive, 3-4 times the "key size" for DSA, ElGamal or Schnorr which amounts for something like 400-2k bits for secure keys.

I also tried with challenge string being some random message encrypted with Prover's public key and the proof being a hash of the message; this yields small response in 6., leaving large message in 3. (at worst I could live with this, using QR codes in 3., scanned instead of being retyped in 4...) and a need for additionally protecting the original random message in the System.

I'm not much into crypto, so maybe I'm missing some other schemes useful here, like 3-way protocols or other stuff.

5
  • This sounds more or less like TOTP, except that you would perhaps want to use a challenge instead of time as the input parameter?
    – vidarlo
    Jan 17, 2023 at 14:24
  • OTP assumes common shared secret -- it's a no option for me; there must be some part of information on the Prover that is not present on the System
    – pwes
    Jan 17, 2023 at 14:56
  • 3
    I don't quite understand that constraint; if the system can't be trusted to keep a secret, how can you trust it to not be modified to accept faked values?
    – vidarlo
    Jan 17, 2023 at 14:59
  • Being able to read value is not the same as being able to modify it. If the user could read the secret, even without changing it he could be authenticated by simply calculating the OTP code by himself.
    – pwes
    Jan 17, 2023 at 15:50
  • The other story is that of course the System has to be protected from tampering the key, be it your secret or the public key of the Prover. Let's assume that's the case.
    – pwes
    Jan 17, 2023 at 15:58

3 Answers 3

2

What you're asking for isn't really possible with high security in the lengths you want, though if you relax the length limits a bit it's not too bad. S generates a challenge (should be at least 128 bits), P appends some metadata (username, timestamp, permissions, whatever) to the challenge and then signs it with a 256-bit elliptic curve-based algorithm (I recommend Ed25519), and returns the signature plus whatever metadata S needs from P and can't get from the user (possibly just the timestamp). This will be larger than 256 bits but possibly not by a lot. S reconstructs the signed string, verifies the signature and that the timestamp is recent enough, and lets the user in. You can even avoid the timestamp length cost by using a bucketed timestamp (e.g. a timestamp is always on an exact minute) and then S just checks the last N minutes (where N is something small like five) to see if any of them validate.

Some signature schemes tolerate signature truncation with only a linear loss of entropy, though I'm not sure if that applies to any elliptic curve ones. If it does, you could trade off less than 128 bits of security for less than 256 bits of signature to relay (though metadata length would be fixed). HMACs do have this property, but require symmetric keys (meaning S would have to store secrets, not just public keys).

There are ways to convey the information more easily than typing a bunch of base64. Using dictionary words greatly increases the total number of keystrokes (as each character has way less than base64's six bits of entropy) but for an experienced typist the difficult factor will be remembering and verifying the string rather than the actual typing, and words are way easier in that regard. You could use an app or printout displaying a QR code (or other 2D barcode; there are a number of options) if S has a camera. You could use a hardware device - either a dedicated piece of hardware like a smart card, or a generic USB flashdrive - that does nothing except convey the challenge in one direction and the response in the other. You could use audio from a phone app if S has a microphone or even just a microphone jack.

If you don't need P to be centralized, you can use smart cards, which are tiny hardware security modules with a little bit of programmable capability. A smart card can easily demand user authentication (via a password or similar) that the user enters on S (after plugging in the card), and then do a challenge-response signing as described above with the user's private key (stored on the card and not exportable). This means that user access management needs to be carried out on S itself, because there is no single P that knows about every user, but it's also a lot simpler and more user-friendly while maintaining good security (the main thing you lose, security-wise, is that the audit logs will live on S instead of P and therefore can only be monitored by systems also on or connected to S, plus if you want to revoke a user's access in a hurry and there are multiple independent S you would need to update each one individually which might create a window for attack).

2
  • That's a lot of options, thank you. I also consider QR code in the way you described (other channels like audio or hardware tokens are off the table). I tried searching for "Some signature schemes [that] tolerate signature truncation with only a linear loss of entropy", but could find any - could you provide some link or name of a scheme? Does shortening the signature somehow also weakens the private key somehow, or its strength is not affected by revealed signatures?
    – pwes
    Jan 18, 2023 at 13:03
  • HMAC is the only one I'm (mostly) sure truncates with linear loss of entropy; you might want to ask on crypto.stackexchange about any others. I expect most symmetric MACs/authentication tags (including AEAD cipher modes) to be fine. RSA has sub-linear entropy per bit but also you can't truncate it (impossible to verify a truncated RSA signature). ECDSA/Ed25519 are I think linear but also don't tolerate truncation. Shortening a signature has no impact on the security of the private key (or an adversary would do it for you); it just increases the risk of collisions accidental or brute-forced.
    – CBHacking
    Jan 18, 2023 at 21:11
0

If you want to avoid pre-shared secrets and use PKI, at least in one direction you have to transfer relatively much data to be typed in.

You can do following. The offline application can encrypt the data for the prover and represent them as a QR code. The user should scan it, the app should transfer the data to the prover. Then the prover authenticate the user and in positive case tells the short number, e.g. 6-digit or 8-digit number. User enter this number.

0

Digging deeper into ideas from @CBHacking, I found answers to question What asymetric scheme provides the shortest signature, while being secure? very informative. My picks:

  • BLS (e.g. BLS12-381 used in Ethereum) produces signatures of length 2*n with n-bit security, the same as mentioned HMAC in @CBHacking, but using public-key scheme that suits me better (note: found comments that BLS12-381 can have 117 to 120-bits security instead of 128)
  • The paper https://eprint.iacr.org/2016/911 describes how to produce 110-bits signatures with 80-bit security (but has some functional disadvantages); not really practical for me, but interesting to know the limits

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .