[PATCH 3/5] ima: Fix ima digest hash table key calculation

[Roberto Sassu]

HUAWEI TECHNOLOGIES Duesseldorf GmbH, HRB 56063
Managing Director: Li Peng, Li Jian, Shi Yanli


> -----Original Message-----
> From: Mimi Zohar [mailto:zohar at linux.ibm.com]
> Sent: Thursday, April 23, 2020 6:53 PM
> To: Roberto Sassu <roberto.sassu at huawei.com>
> Cc: linux-integrity at vger.kernel.org; linux-security-module at vger.kernel.org;
> linux-kernel at vger.kernel.org; Krzysztof Struczynski
> <krzysztof.struczynski at huawei.com>; Silviu Vlasceanu
> <Silviu.Vlasceanu at huawei.com>; stable at vger.kernel.org
> Subject: Re: [PATCH 3/5] ima: Fix ima digest hash table key calculation
> 
> On Thu, 2020-04-23 at 10:21 +0000, Roberto Sassu wrote:
> > > Hi Roberto, Krsysztof,
> > >
> > > On Wed, 2020-03-25 at 17:11 +0100, Roberto Sassu wrote:
> > > > From: Krzysztof Struczynski <krzysztof.struczynski at huawei.com>
> > > >
> > > > Function hash_long() accepts unsigned long, while currently only one
> byte
> > > > is passed from ima_hash_key(), which calculates a key for ima_htable.
> > > Use
> > > > more bytes to avoid frequent collisions.
> > > >
> > > > Length of the buffer is not explicitly passed as a function parameter,
> > > > because this function expects a digest whose length is greater than
> the
> > > > size of unsigned long.
> > >
> > > Somehow I missed the original report of this problem https://lore.kern
> > > el.org/patchwork/patch/674684/.  This patch is definitely better, but
> > > how many unique keys are actually being used?  Is it anywhere near
> > > IMA_MEASURE_HTABLE_SIZE(512)?
> >
> > I did a small test (with 1043 measurements):
> >
> > slots: 250, max depth: 9 (without the patch)
> > slots: 448, max depth: 7 (with the patch)
> 
> 448 out of 512 slots are used.
> 
> >
> > Then, I increased the number of bits to 10:
> >
> > slots: 251, max depth: 9 (without the patch)
> > slots: 660, max depth: 4 (with the patch)
> 
> 660 out of 1024 slots are used.
> 
> I wonder if there is any benefit to hashing a digest, instead of just
> using the first bits.

Before I calculated max depth until there is a match, not the full depth.

#1
return hash_long(*((unsigned long *)digest), IMA_HASH_BITS);
#define IMA_HASH_BITS 9

Runtime measurements: 1488
Violations: 0
Slots (used/available): 484/512
Max depth hash table: 10

#2
return *(unsigned long *)digest % IMA_MEASURE_HTABLE_SIZE;
#define IMA_HASH_BITS 9

Runtime measurements: 1491
Violations: 2
Slots (used/available): 489/512
Max depth hash table: 10

#3
return hash_long(*((unsigned long *)digest), IMA_HASH_BITS);
#define IMA_HASH_BITS 10

Runtime measurements: 1489
Violations: 0
Slots (used/available): 780/1024
Max depth hash table: 6

#4
return *(unsigned long *)digest % IMA_MEASURE_HTABLE_SIZE;
#define IMA_HASH_BITS 10

Runtime measurements: 1489
Violations: 0
Slots (used/available): 793/1024
Max depth hash table: 6

Roberto

HUAWEI TECHNOLOGIES Duesseldorf GmbH, HRB 56063
Managing Director: Li Peng, Li Jian, Shi Yanli


> > > Do we need a new securityfs entry to display the number used?
> >
> > Probably it is useful only if the administrator can decide the number of
> slots.
> 
> The securityfs suggestion was just a means for triggering the above
> debugging info you provided.  Could you provide another patch with the
> debugging info?
> 
> thanks,
> 
> Mimi