Re: IMA and PQC

[Stefan Berger <stefanb@linux.ibm.com>]

On 2/26/26 2:44 PM, Eric Biggers wrote:
> On Thu, Feb 26, 2026 at 02:21:41PM -0500, Stefan Berger wrote:
>>
>>
>> On 2/26/26 1:32 PM, Eric Biggers wrote:
>>> On Thu, Feb 26, 2026 at 12:22:32PM -0500, Stefan Berger wrote:
>>>>> I see that IMA indeed never upgraded full file hashes to use
>>>>> 'struct ima_file_id'.  Building a new feature that relies on this seems
>>>>> like a bad idea though, given that it's a security bug that makes the> IMA
>>>> protocol cryptographically ambiguous.  I.e., it means that in IMA,
>>>>> when the contents of some file are signed, that signature is sometimes
>>>>> also valid for some other file contents which the signer didn't intend.
>>>>
>>>> You mean IMA should not sign the digest in the ima_file_id structure but
>>>> hash the ima_file_id structure in which this file digest is written into
>>>> (that we currently sign) and sign/verify this digest? And we would do this
>>>> to avoid two different files (with presumably different content) from having
>>>> the same hashes leading to the same signature? Which hashes (besides the
>>>> non-recommended ones) are so weak now that you must not merely sign a file's
>>>> hash?
>>>>
>>>> The problem with this is that older kernels (without patching) won't be able
>>>> to handle newer signatures.
>>>
>>> IMA needs to sign the entire ima_file_id structure, which is indeed what
>>> IMA already does when it uses that structure.  (Well, actually it signs
>>> a hash of the struct, but that's best thought of an implementation
>>> detail of legacy signature algorithms that can only sign hashes.  For a
>>> modern algorithm the whole struct should be passed instead.)  Just IMA
>>> uses that structure only for fsverity hashes, which is a bug that makes
>>> the IMA protocol ambiguous.  It needs to use ima_file_id consistently,
>>> otherwise a signed message sometimes corresponds to multiple unique file
>>> contents even without a break in the cryptographic hash function.
>>
>> Before we jump into making changes on this old stuff I think it's good to
>> understand the underlying problem and the likelyhood of signatures
>> validating different data, such as a file and fsverity data. How likely is
>> this?
>>
>> Assuming a strong hash I suppose that is not a concern with RSA because here
>> the digest is padded and then directly encrypted with the private key. Upon
>> verification (pub key decrypt) we would unpad and memcmp the digests.
>>
>> Again, assuming a strong hash: With ECDSA NIST P256 for example we have a 32
>> byte signature. With a SHA512 being used for hashing for example we would be
>> doing a projection of a 64byte hash space to a 32byte signature space with.
>> Just by this projection of a much larger space into a smaller space
>> signatures that validate multiple input data could be a problem. One 'easy'
>> case where signatures for different input data is the same (not exactly the
>> same due to nonce involved the signature is verifyable), albeit unlikely, is
>> that there could be different input data for the SHA512 that lead to the
>> same 32bytes prefix, which is then used after truncating the sha512 to the
>> first 32 bytes for the ECDSA signature, and this then leads to a signature
>> that is verifyable for different input data. So that's the 'simple' case at
>> least for this thought experiment for a non-expert.
>>
>> Now what should still be difficult to do is given a file and a hash-to-use
>> that you can create fsverity content that leads to a hash that in turn leads
>> to a NIST-P256 signature that can be used for signature verification(s) of
>> the file and the totally different fsverity data. Is this a problem that is
>> as difficult to solve just as finding different input data for a hash that
>> leads to the same digest?
> 
> There's no differentiation between a 'struct ima_file_id' that
> *represents* the contents of some file, and a file whose contents are
> *equal to* that 'struct ima_file_id' and that uses a full-file hash.  In
> both cases the same key and message are used for signing and verifying.

I hadn't been thinking of this... It's a side-effect of starting to sign 
ima_file_id for v3 that a file *content* could now hold the ima_file_id 
structure (as signed with v3) and the signature would validate when used 
with the v2 signature verification scheme. So, the content of the file 
would presumably be odd/useless (2 bytes + hash) but it would verify 
with the signature created for v3. We will have to offer the possibility 
to move to v3 signatures for all signing schemes and offer the 
possibility to deactivate older versions (<v3).

> 
> This means that every time a file is signed using the ima_file_id
> scheme, it also implicitly signs some other file contents, which an
> attacker can freely replace the file with.  Similarly, every time a file
> that happens to be a valid ima_file_id is signed using the older scheme,
> it also implicitly signs the contents that the ima_file_id correspond
> to, which the attacker can freely replace the file with.  In either
> case, no collision in the cryptographic hash function is required.
> 
> It's simply a broken protocol.  To fix this, IMA must only support
> signatures that use the ima_file_id scheme.
> 
> Of course, that will require making them support full-file hashes and
> not just fsverity hashes.  If I recall correctly, this was actually part
> of the original design of the ima_file_id-based signatures.  It's
> unclear why the implementation is still incomplete.
> 
> - Eric