Return to Answer

I read the question as: there is an RSA-based signature verification scheme that takes alleged signature $s$, computes alleged message representative $r=s^e\bmod n$ where $(n,e)$ is the public key, formats $r$ as 448+106+1-43 = 512 bytes (consistent with $n$ of 4096-bit), compares bytes 43 to 106 (that is 64 bytes or 512 bits) of $r$ to the (e.g. SHA-512) hash $h$ of the alleged message, and accepts the message on match.

Other bytes in the message representative $r$ are supposed to be filled in some unspecified way by the signer, e.g. randomly or pseudo-randomly, but they are not checked by the verifier.

An attack is possible at least for low $e$, e.g. $e\in\{3,5,7\}$ or slightly more.

Assuming big-endian conversion of integers to bytes, and bytes in $r$ are numbered from the left starting at index 0 for the high-order byte, there are 512-1-106 = 405 bytes or $b=3240$ bits on the right of the verified portion, thus any $r$ of the form $h\cdot2^b+x$ with $0\le x<2^b$ is acceptable. If we can make an $s$ with $s^e$ such an $r$, it is accepted.

For $e\le7$, computing the hash $h$ of an arbitrary message then $s=\left\lceil\sqrt[e]{h⋅2^b}\,\right\rceil$ will do.

That signature scheme is not an academically recognized one. It's definitely is not recommendable. And as the saying attributed to the NSA by Bruce Schneier goes: “Attacks only get better; they never get worse”. Thus as often, the correct solution is not to increase $e$. It's to use proper RSA signature padding, e.g. RSASSA-PSS.

If someone used this “in a bootloader secureboot verification process”, then they are incompetent (including careless), or intend the system to be vulnerable. In the later case and if they used $e>7$, then I wish I knew what they had in mind, and towards this more details, like the value of $e$.

I read the question as: there is an RSA-based signature verification scheme that takes alleged signature $s$, computes alleged message representative $r=s^e\bmod n$ where $(n,e)$ is the public key, formats $r$ as 448+106+1-43 = 512 bytes (consistent with $n$ of 4096-bit), compares bytes 43 to 106 (that is 64 bytes or 512 bits) of $r$ to the (e.g. SHA-512) hash $h$ of the alleged message, and accepts the message on match.

Other bytes in the message representative $r$ are supposed to be filled in some unspecified way by the signer, e.g. randomly or pseudo-randomly, but they are not checked by the verifier.

An attack is possible at least for low $e$, e.g. $e\in\{3,5,7\}$ or slightly more.

Assuming big-endian conversion of integers to bytes, and bytes in $r$ are numbered from the left starting at index 0 for the high-order byte, there are 512-1-106 = 405 bytes or $b=3240$ bits on the right of the verified portion, thus any $r$ of the form $h\cdot2^b+x$ with $0\le x<2^b$ is acceptable. If we can make an $s$ with $s^e$ such an $r$, it is accepted.

For $e\le7$, computing the hash $h$ of an arbitrary message then $s=\left\lceil\sqrt[e]{h⋅2^b}\,\right\rceil$ will do.

That signature scheme is not an academically recognized one. It's definitely not recommendable. And as the saying attributed to the NSA by Bruce Schneier goes: “Attacks only get better; they never get worse”. Thus as often, the correct solution is not to increase $e$. It's to use proper RSA signature padding, e.g. RSASSA-PSS.

If someone used this “in a bootloader secureboot verification process”, then they are incompetent (including careless), or intend the system to be vulnerable. In the later case and if they used $e=F_4=65537$, then I wish I knew what they had in mind.

I read the question as: there is an RSA-based signature verification scheme that takes alleged signature $s$, computes alleged message representative $r=s^e\bmod n$ where $(n,e)$ is the public key, formats $r$ as 448 bytes (thus presumably $n$ is 3584-bit or just below that), compares bytes 43 to 106 (that is 64 bytes or 512 bits) of $r$ to the (e.g. SHA-512) hash $h$ of the alleged message, and accepts the message on match.

Other bytes in the message representative $r$ are supposed to be filled in some unspecified way by the signer, e.g. randomly or pseudo-randomly, but they are not checked by the verifier.

An attack is possible at least for low $e$, e.g. $e=3$, $e=5$ or slightly more.

Assuming big-endian conversion of integers to bytes, and bytes in $r$ are numbered from the left starting at index 0 for the high-order byte, there are 448-1-106 = 341 bytes or $b=2728$ bits on the right of the verified portion, thus any $r$ of the form $h\cdot2^b+x$ with $0\le x<2^b$ is acceptable. If we can make an $s$ with $s^e$ such an $r$, it is accepted.

For $e\le5$, computing the hash $h$ of an arbitrary message then $s=\left\lceil\sqrt[e]{h⋅2^b}\,\right\rceil$ will do.

That signature scheme is not an academically recognized one. It's definitely is not recommendable. And as the saying attributed to the NSA by Bruce Schneier goes: “Attacks only get better; they never get worse”. Thus as often, the correct solution is not to increase $e$. It's to use proper RSA signature padding, e.g. RSASSA-PSS.

If someone used this “in a bootloader secureboot verification process”, then they are incompetent (including careless), or intend the system to be vulnerable. In the later case and if they used $e>5$, then I wish I knew what they had in mind, and towards this more details, like the value of $e$.

I read the question as: there is an RSA-based signature verification scheme that takes alleged signature $s$, computes alleged message representative $r=s^e\bmod n$ where $(n,e)$ is the public key, formats $r$ as 448+106+1-43 = 512 bytes (consistent with $n$ of 4096-bit), compares bytes 43 to 106 (that is 64 bytes or 512 bits) of $r$ to the (e.g. SHA-512) hash $h$ of the alleged message, and accepts the message on match.

Other bytes in the message representative $r$ are supposed to be filled in some unspecified way by the signer, e.g. randomly or pseudo-randomly, but they are not checked by the verifier.

An attack is possible at least for low $e$, e.g. $e\in\{3,5,7\}$ or slightly more.

Assuming big-endian conversion of integers to bytes, and bytes in $r$ are numbered from the left starting at index 0 for the high-order byte, there are 512-1-106 = 405 bytes or $b=3240$ bits on the right of the verified portion, thus any $r$ of the form $h\cdot2^b+x$ with $0\le x<2^b$ is acceptable. If we can make an $s$ with $s^e$ such an $r$, it is accepted.

For $e\le7$, computing the hash $h$ of an arbitrary message then $s=\left\lceil\sqrt[e]{h⋅2^b}\,\right\rceil$ will do.

That signature scheme is not an academically recognized one. It's definitely is not recommendable. And as the saying attributed to the NSA by Bruce Schneier goes: “Attacks only get better; they never get worse”. Thus as often, the correct solution is not to increase $e$. It's to use proper RSA signature padding, e.g. RSASSA-PSS.

If someone used this “in a bootloader secureboot verification process”, then they are incompetent (including careless), or intend the system to be vulnerable. In the later case and if they used $e>7$, then I wish I knew what they had in mind, and towards this more details, like the value of $e$.

I read the question as: there is an RSA-based signature verification scheme that takes alleged signature $s$, computes alleged message representative $r=s^e\bmod n$ where $(n,e)$ is the public key, formats $r$ as 448 bytes (thus presumably $n$ is 3584-bit or just below that), compares bytes 43 to 106 (that is 64 bytes or 512 bits) of $r$ to the (e.g. SHA-512) hash $h$ of the alleged message, and accepts the message on match.

Other bytes in the message representative $r$ are supposed to be filled in some unspecified way by the signer, e.g. randomly or pseudo-randomly, but they are not checked by the verifier.

An attack is possible at least for low $e$, e.g. $e=3$, $e=5$ or slightly more.

Assuming big-endian conversion of integers to bytes, and bytes in $r$ are numbered from the left starting at index 0 for the high-order byte, there are 448-1-106 = 341 bytes or $b=2728$ bits on the right of the verified portion, thus any $r$ of the form $h\cdot2^b+x$ with $0\le x<2^b$ is acceptable. If we can make an $s$ with $s^e$ such an $r$, it is accepted.

For $e\le5$, computing the hash $h$ of an arbitrary message then $s=\left\lceil\sqrt[e]{h⋅2^b}\,\right\rceil$ will do.

That's not an academically recognized scheme, and definitely is not recommendable. And as the saying attributed to the NSA by Bruce Schneier goes: “Attacks only get better; they never get worse”. Thus as often, the correct solution is not to increase $e$. It's to use proper RSA signature padding, e.g. RSASSA-PSS.

If someone used it this “in a bootloader secureboot verification process”, then they are incompetent (including careless), or intend the system to be vulnerable. In the later case and if they used $e>5$, then I wish I knew what they had in mind, and towards this more details, like the value of $e$.

I read the question as: there is an RSA-based signature verification scheme that takes alleged signature $s$, computes alleged message representative $r=s^e\bmod n$ where $(n,e)$ is the public key, formats $r$ as 448 bytes (thus presumably $n$ is 3584-bit or just below that), compares bytes 43 to 106 (that is 64 bytes or 512 bits) of $r$ to the (e.g. SHA-512) hash $h$ of the alleged message, and accepts the message on match.

Other bytes in the message representative $r$ are supposed to be filled in some unspecified way by the signer, e.g. randomly or pseudo-randomly, but they are not checked by the verifier.

An attack is possible at least for low $e$, e.g. $e=3$, $e=5$ or slightly more.

Assuming big-endian conversion of integers to bytes, and bytes in $r$ are numbered from the left starting at index 0 for the high-order byte, there are 448-1-106 = 341 bytes or $b=2728$ bits on the right of the verified portion, thus any $r$ of the form $h\cdot2^b+x$ with $0\le x<2^b$ is acceptable. If we can make an $s$ with $s^e$ such an $r$, it is accepted.

For $e\le5$, computing the hash $h$ of an arbitrary message then $s=\left\lceil\sqrt[e]{h⋅2^b}\,\right\rceil$ will do.

That signature scheme is not an academically recognized one. It's definitely is not recommendable. And as the saying attributed to the NSA by Bruce Schneier goes: “Attacks only get better; they never get worse”. Thus as often, the correct solution is not to increase $e$. It's to use proper RSA signature padding, e.g. RSASSA-PSS.

If someone used this “in a bootloader secureboot verification process”, then they are incompetent (including careless), or intend the system to be vulnerable. In the later case and if they used $e>5$, then I wish I knew what they had in mind, and towards this more details, like the value of $e$.