1
$\begingroup$

I read about bactracking resistance:

http://cs.yale.edu/publications/techreports/tr1466.pdf

https://arxiv.org/pdf/1810.02227.pdf

https://www.schneier.com/wp-content/uploads/2017/10/paper-prngs.pdf

Story (Motivational Story) in first paper is interesting. But seems to be theoretical.

Backtracking resistance is critical to applications requiring long-term security of past outputs.

Any examples? Is this useful in some key-agreement protocol? Do we use it somewhere? I know we use forward secrecy in some protocols:

https://en.wikipedia.org/wiki/Forward_secrecy

But what with backward secrecy? Can it be alternative to public key cryptography as they wrote here:

Initially, they thought to use a public key encryption scheme but quickly got tired of the need to exchange their public keys so frequently. Then, Alice suggested they each use a cryptographically secure pseudorandom bit generator initialized with the same secret seed to generate the same key for a symmetric encryption algorithm. After exchanging the secret seed, Alice and Bob each used the pseudorandom bit generator on their respective computers and decided to generate a fresh AES [3] key every day.

If RSA will be broken by quantum computers, can this approach be some kind of solution?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Note that using a deterministic random bit generator (DRBG) for this is an extremely bad idea. Don't confuse the term CSPRNG with the random number generators provided by runtimes. It makes more sense to e.g. use a KDF with a counter so that you know for sure that the DRBG doesn't go out of sync, and to be able to re-sync if it does. $\endgroup$
    – Maarten Bodewes ♦
    Sep 23, 2022 at 10:07
  • $\begingroup$ Using a stream cipher instead of a CSPRNG could also work, providing that the key generation is identical on both systems. AES just consists of random bits, so generally that is true. However, if you look at RSA. Another related algorithm would be a (double) key ratchet. $\endgroup$
    – Maarten Bodewes ♦
    Sep 23, 2022 at 10:09
  • $\begingroup$ A clear confusion about the concepts. Forward secrecy considers the security of the back messages even under the compromise of the master key and that still requires the deletion of the keys. $\endgroup$
    – kelalaka
    Sep 23, 2022 at 17:33

1 Answer 1

Reset to default
3
$\begingroup$

No, because there still needs to be one key exchange, and if an adversary can get this very first key, he is able to compute every other key by simulating the pseudorandom bit generator.

The idea of this approach is not to be an alternative to public key exchange, but to reduce the key exchange in protocols and applications, which depend on repetitively exchanging or creating new keys.

Improve this answer
$\endgroup$
4
  • $\begingroup$ True, I forgot they have to exchange keys at least one time, but of course they can do it in other, even costly and slowly way. It still can be good alternative - if bactracking PRNG itself is good solution for broken public key cryptography. $\endgroup$
    – Tom
    Sep 23, 2022 at 9:31
  • $\begingroup$ Yes, the PQ-secure key exchanges we know so far are very slow, compared to the currently used applications. If we don't find any better algorithms, backtracking prng could become important. $\endgroup$
    – Titanlord
    Sep 23, 2022 at 9:34
  • $\begingroup$ By the way hash functions could be bactracking resistant if we would use them repetitively, isn't it? If they can work with 25 cycles per byte I suspect it could be enough for every application. Or do we need something even faster? Of course such a hash function generator has unknown period and this is dangerous (it can stuck in short cycle), but this can be trivially resolved, by combining the state with counter or Weyl sequence. $\endgroup$
    – Tom
    Sep 23, 2022 at 9:54
  • $\begingroup$ A hash only has one message as input. What you want is a KDF, although KDF1 and 2 consist of simply a hash and a statically sized counter (in their most simple form). Obviously if you just hash the initial secret/seed you'd get the same key over and over :) $\endgroup$
    – Maarten Bodewes ♦
    Sep 23, 2022 at 10:15

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.