Cryptology ePrint Archive: Report 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. This report tries to validate the intuition that remixed keys are not easy to surmise, in other words, that remixing does not introduce an exploitable spike in the probability distribution of the remixed key. 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. The proofs are derived from a proof of an asymptotic result on probability theory in a textbook by Shoup.

Category / Keywords: foundations / Key derivation, entropy

Date: received 20 Apr 2015, last revised 7 May 2015

Contact author: dbrown at certicom com

Available format(s): PDF | BibTeX Citation

Note: Added Theorem 9: an easier, weaker but still useful upper bound.

Version: 20150507:192141 (All versions of this report)

Short URL: ia.cr/2015/375

Discussion forum: Show discussion | Start new discussion