Paper 2015/375

Bounds on surmising remixed keys

Daniel R. L. Brown

Abstract

A remixed key is derived from a secret source key by applying a public but unpredictable random function to the source key. A remixed key models a key derived from a shared secret and a public unpredictable salt, using a common, deterministic, pseudorandom function---which is somewhat like TLS record-layer keys, for example. This report tries to validate the intuition that remixed keys are not easy to surmise due to publicity of the remixing function, in other words, that remixing does not introduce an exploitable spike in the probability distribution of the remixed key relative to the remix function. The report provides pencil-and-paper proofs of numerical bounds on the probability that an adversary can surmise a remixed key, assuming a uniformly random source key and remix function. Some proofs are derived from a proof of an asymptotic result on probability theory (a balls-in-bins bound) in a textbook by Shoup.

Note: Added reference to Raab and Steger. Added phrase to abstract.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Key derivationentropy
Contact author(s)
dbrown @ certicom com
History
2018-05-07: last of 6 revisions
2015-04-24: received
See all versions
Short URL
https://ia.cr/2015/375
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/375,
      author = {Daniel R.  L.  Brown},
      title = {Bounds on surmising remixed keys},
      howpublished = {Cryptology ePrint Archive, Paper 2015/375},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/375}},
      url = {https://eprint.iacr.org/2015/375}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.