ECDSA: with knowledge of private key, can we make signatures with partially chosen content?

Question

In ECDSA, with knowledge of private key, can we make signatures with partially chosen content?

Detailing that: In ECDSA (with secp256r1 curve and SHA-256 hash), assume we know the private key, the message, and can choose the per-signature random. It that helps, assume we can choose the private key, and some of the message, so that it's hash is essentially random. Can we (more efficiently than by trial and error) make a signature $S=(r,s)$ valid for one key and message that, expressed as two 32-byte bytestrings concatenated, contains a bytestring that we can choose, or with certain characteristics?

---

Context: I'm helping (un-retributed) a standardization working group defining a cryptographically signed 2D code, and I try to make test cases where certain byte strings occur that could trigger incompatibilities between code generators and scanners. A simplified characterization is that there occurs in the signature a sequence of at least $u$ (like 3 to 7) bytes in a set of $v$ (10 to 13) values. That has probability about $(v/256)^u\,(65-u)$ to occur by chance, which gets tiny when $u$ increases. I'm not afraid of forgeries: The overall aim is testing out code encoders that could cause failures on the field (e.g. passengers blocked from boarding) because the combination of data and signature hits a corner case in some decoders.

^{Off-topic: there's rudimentary data compression built into most 2D codes. In Aztec aka ISO/IEC 24778:2008, encoders are encouraged to switch to Digit mode when long-enough bytestring segments consist of bytes in a set corresponding to ASCII 0123456789,. which get encoded as 4 bit/byte. When other bytes occur between two such sequences, it can be used Byte Shift that "can encode either isolated extended ASCII or control characters or long strings of byte data, possibly filling the whole symbol. At the end of the byte string, encoding returns to the mode from which B/S was invoked". In Digit mode there's no direct way to Byte Shift, this is done thru Upper/Lock or Upper/Shift (the later designed to insert a single uppercase ASCII letter in a sequence of digits). At the end of a Byte Shift entered from Digit mode thru Upper/Shift, decoders vary about if they return to Digit mode or Upper mode, and all hell breaks loose. Below is a minimal example that used to decode to ASCII 333j+33333 for ZXing (before version 3.2.2 of 8 Aug 2016) but 333j+ITIT for NeoReader and some others.}

.

Answer 1

If the attacker has the ability of choosing the private key, then he can create a valid signature $(r,s)$ with a target value for $s$ for any message $m$. The attack works in the following way:

The attacker choose its target $s$, generates a random ephemeral key $k$ and computes the hash of the message $e = H(m)$. Then the attacker computes the scalar multiplication $kG$ and takes $r$ as the x-coordinate of the result modulo $n$. Then he computes the private key $d$ as: $d = \frac{s - k^{-1}e}{k^{-1}r}$.

In this way $s$, when computed in the standard way: $s = k^{-1}(e+rd)$ will match the desired $s$.

In case the attacker can't choose the private key then I don't see how he can achieve his goal because in $k^{-1}(e+rd)$ he can control only $k^{-1}$ but that will pseudo-randomly influence the value of $r$.