3
$\begingroup$

I want to construct a hash-chain where I want to share millions of small AES-128 keys with Bob over a period of time. Bob should not be able to predict the future keys if he knows the past keys. I also want to avoid having Bob storing all these keys, but rather be able to derive them so that if they know the key from time $t$, they should be able to derive the keys from time $t-1, t-2$, and so on. So, future-to-past derivation should be possible. Past-to-future derivation should be hard.

The hash-chain way of doing this is to start with a random string, hash it with sha256, say, 1 million times, and start the chain with the 1 millionth hash. This way, if Bob is at the 10th iteration of our protocol, and wants to go back to the 6th iteration, he hashes the 10th iteration key 4 times to get the 6th key.

I am wondering if we can do the same with some encryption scheme like RSA. I give Bob my RSA public key $([e, n])$. I start the chain with a large random number in the range $(2, n-1)$, and decrypt it. I am assuming that every number in this range has a valid decryption. This decryption chain can continue as many times. If Bob wants to reconstruct keys, he uses the encryption algorithm, for which he has the public key. I can use some KDF to derive the AES-128 key from this large RSA "number".

Is the RSA-chain scheme as safe as the SHA-chain scheme?

$\endgroup$
  • $\begingroup$ Seems like "Related questions" from stackexchange works great. I got what I was looking for here: crypto.stackexchange.com/questions/1793/… $\endgroup$ – Tejaswi Nadahalli Aug 16 at 8:20
  • $\begingroup$ This question also feels closely related. $\endgroup$ – Ilmari Karonen Aug 16 at 12:40
  • $\begingroup$ Seekable sequential key generators (SSKG), used in reverse order (start from a very high counter value, give them one key at a time counting backwards in the SSKG output, and when given any one key they can recreate all past keys / later SSKG values). eprint.iacr.org/2013/397 $\endgroup$ – Natanael Aug 17 at 12:43
3
$\begingroup$

The proposed system seems to be as follows:

  • At generation, Alice selects odd $e>2$ and random large primes $p$ and $q$ with $\gcd(p-1,e)=1=\gcd(q-1,e)$; computes $n\gets p\,q$; chooses random $s_0$ in $[1,n)$; and publishes $(n,e,s_0)$. She computes and keeps secret $\lambda(n)\gets(p-1)(q-1)/\gcd(p-1,q-1)$ and $d\gets e^{-1}\bmod\lambda(n)$.
  • For successive times $t\in\Bbb N^*$, Alice computes $s_t\gets{s_{t-1}}^d\bmod n$ and publishes $s_t$ at time $t$.
  • For $t\in\Bbb N^*$, anyone with knowledge of $(n,e,s_{t-1})$, e.g. Bob, can check an alleged $s_t$, by verifying that $0<s_t<n$ and ${s_t}^e\bmod n=s_{t-1}$. Alternatively, $s_t$ can be verified from $(n,e,s_0)$ by verifying that $0<s_t<n$ and ${s_t}^{(e^t)}\bmod n=s_0$.
  • By convention, $k_t=H(s_t)$ where $H$ is some 128-bit PRF, e.g. the low-order 128 bits of SHA-256.

Anyone with knowledge and trust of $(n,e,s_0)$ and knowledge of $s_{t'}$, e.g. Bob, can compute and trust $k_t$ for $0\le t\le t'$. The intention is that it would be infeasible to derive $k_t$ for $t>t'$. That holds, with some degree of reduction to the RSA problem. Some arguments:

  • Given how it is generated, it is overwhelmingly likely that $s_0$ is coprime to both $p$ and $q$. Assuming that, it follows that for fixed $t$, each $s_t$ is uniformly random in $\Bbb Z_n^*$.
  • Knowledge of $s_{t'}$ subsumes knowledge of earlier $s_i$ with $i<t'$.
  • Finding $s_t$ from $s_{t'}$ for $t>t'$ is solving the RSA problem for public exponent $e^{t-t'}$, or equivalently public exponent $e^{t-t'}\bmod\lambda(n)$, which itself takes quite random-like values in $\Bbb Z_{\lambda(n)}^*$.
$\endgroup$
  • $\begingroup$ Wait... I tried following your insecurity argument with $t=1 > t'=0$ (i.e. Alice only publishes $n$, $e$ and $s_0$, Bob wants to compute $s_1 = s_0^d \bmod n$), but it seems to me that Bob being able to compute $s_1$ in that case would be directly equivalent to breaking RSA. Now I'm confused. :/ $\endgroup$ – Ilmari Karonen Aug 16 at 17:36
  • $\begingroup$ @Ilmari Karonen: You are of course totally right. Fixed now. Somewhat I wrote ${s_t}^{(t\,e)}\bmod n=s_0$ when really ${s_t}^{(e^t)}\bmod n=s_0$. Oups. $\endgroup$ – fgrieu Aug 17 at 10:23
  • 1
    $\begingroup$ Ah, a typo. That happens. :) Anyway, thinking about this a bit more, it seems like a reduction should be possible. Basically, if Alice knew that Bob could break this scheme by predicting $s_{t+1}=s_t^d$ when given $(n,e,s_0,\dots,s_t)$, then she could use Bob as an oracle to break RSA encryption by taking a ciphertext $c$ encrypted with the public key $(n,e)$, generating $(s_t, s_{t-1}, s_{t-2}, \dots, s_0) = (c, c^e, c^{e^2}, \dots, c^{e^t})$ and sending those (along with $n$ and $e$) to Bob. $\endgroup$ – Ilmari Karonen Aug 17 at 10:54
  • $\begingroup$ See my other comment, SSKG:s are relevant eprint.iacr.org/2013/397 $\endgroup$ – Natanael Aug 17 at 12:44
  • $\begingroup$ @fgrieu I saw your earlier comment and was about to remark on the typo, but then your answer disappeared :-). Now, it's back again, and seems like everything is ok. $\endgroup$ – Tejaswi Nadahalli Aug 19 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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