How deeply does Hacking Cryptography cover prefix cube root?

Explains prefix search, suffix matching, stitching, retries, and executable Go tests, while stopping short of full verifier internals.

Prefix cube root

As explained in Hacking Cryptography

A prefix cube root is a candidate RSA signature value whose cube preserves a required prefix of an encoded message despite unconstrained or truncated trailing bits.

A prefix cube root finds a candidate RSA signature s whose cube begins with a chosen byte sequence. The trailing bytes may be garbage, which makes the technique useful when RSA uses e = 3 and PKCS#1 v1.5 padding validation is incomplete. section 9.6.3 section 9.7

The attack technique proceeds in three stages:

Choose the fixed header bytes, such as 00 01, and append random bytes to form a large target value. section 9.6.4
Use bisection search to find a cube root whose cube preserves the target’s most significant bytes; discard its right-hand spillover. section 9.6.3
Place the complete suffix cube root after the trimmed prefix root, leaving the unconstrained garbage in the middle. section 9.6.4

Forged signature test

A Go test generates an RSA key with public exponent 3, hashes “Hello World!” with SHA-256, constructs a forged signature, and verifies it through an insecure PKCS#1 v1.5 verifier.

The failure is not caused by calculating a cube root alone. It arises when a low public exponent combines with a verifier that checks only selected encoded-message bytes instead of requiring every PKCS#1 v1.5 padding byte to be FF. section 9.7 section 9.6.4

How Hacking Cryptography covers it

liveBook manning.com

Read Hacking Cryptography on liveBook Get the book at manning.com

Related concepts

Bleichenbacher's e=3 forgery attackpart of · Bleichenbacher's e=3 forgery attack is an RSA signature-forgery attack that exploits lax validation of PKCS #1 v1.5 signature padding when the public exponent is 3.
signature forgery attackpart of · A signature forgery attack produces a signature that a verifier accepts as authentic without authorization from the legitimate signer's private key.
bisection methoduses · A root-finding technique that repeatedly halves an interval according to whether a candidate is below or above the target.

This explainer was generated by Manning's knowledge graph from the text of Hacking Cryptography. The section links point to the parts of the book it draws on.