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

Commit Message

Roberto Sassu March 25, 2020, 4:11 p.m. UTC

From: Krzysztof Struczynski <[e-mail]>

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.

Cc: [e-mail]
Fixes: 3323eec921ef ("integrity: IMA as an integrity service provider")
Signed-off-by: Krzysztof Struczynski <[e-mail]>
---
 security/integrity/ima/ima.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

Comments

Mimi Zohar April 22, 2020, 8:56 p.m. UTC | #1

Hi Roberto, Krsysztof,

On Wed, 2020-03-25 at 17:11 +0100, Roberto Sassu wrote:
> From: Krzysztof Struczynski <[e-mail]>
> 
> 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)?

Do we need a new securityfs entry to display the number used?

Mimi

> 
> Cc: [e-mail]
> Fixes: 3323eec921ef ("integrity: IMA as an integrity service provider")
> Signed-off-by: Krzysztof Struczynski <[e-mail]>
> ---
>  security/integrity/ima/ima.h | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/security/integrity/ima/ima.h b/security/integrity/ima/ima.h
> index 64317d95363e..cf0022c2bc14 100644
> --- a/security/integrity/ima/ima.h
> +++ b/security/integrity/ima/ima.h
> @@ -177,7 +177,7 @@ extern struct ima_h_table ima_htable;
>  
>  static inline unsigned long ima_hash_key(u8 *digest)
>  {
> -	return hash_long(*digest, IMA_HASH_BITS);
> +	return hash_long(*((unsigned long *)digest), IMA_HASH_BITS);
>  }
>  
>  #define __ima_hooks(hook)		\

Roberto Sassu April 23, 2020, 10:21 a.m. UTC | #2

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


> -----Original Message-----
> From: Mimi Zohar [mailto:[e-mail]]
> Sent: Wednesday, April 22, 2020 10:56 PM
> To: Roberto Sassu <[e-mail]>
> Cc: [e-mail]; [e-mail];
> [e-mail]; Krzysztof Struczynski
> <[e-mail]>; Silviu Vlasceanu
> <[e-mail]>; [e-mail]
> Subject: Re: [PATCH 3/5] ima: Fix ima digest hash table key calculation
> 
> Hi Roberto, Krsysztof,
> 
> On Wed, 2020-03-25 at 17:11 +0100, Roberto Sassu wrote:
> > From: Krzysztof Struczynski <[e-mail]>
> >
> > 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)

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)

> 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.

Roberto

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


> > Cc: [e-mail]
> > Fixes: 3323eec921ef ("integrity: IMA as an integrity service provider")
> > Signed-off-by: Krzysztof Struczynski <[e-mail]>
> > ---
> >  security/integrity/ima/ima.h | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> >
> > diff --git a/security/integrity/ima/ima.h b/security/integrity/ima/ima.h
> > index 64317d95363e..cf0022c2bc14 100644
> > --- a/security/integrity/ima/ima.h
> > +++ b/security/integrity/ima/ima.h
> > @@ -177,7 +177,7 @@ extern struct ima_h_table ima_htable;
> >
> >  static inline unsigned long ima_hash_key(u8 *digest)
> >  {
> > -	return hash_long(*digest, IMA_HASH_BITS);
> > +	return hash_long(*((unsigned long *)digest), IMA_HASH_BITS);
> >  }
> >
> >  #define __ima_hooks(hook)		\

Mimi Zohar April 23, 2020, 4:53 p.m. UTC | #3

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 <[e-mail]>
> > >
> > > 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. 

> 
> > 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

Roberto Sassu April 24, 2020, 12:18 p.m. UTC | #4

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


> -----Original Message-----
> From: Mimi Zohar [mailto:[e-mail]]
> Sent: Thursday, April 23, 2020 6:53 PM
> To: Roberto Sassu <[e-mail]>
> Cc: [e-mail]; [e-mail];
> [e-mail]; Krzysztof Struczynski
> <[e-mail]>; Silviu Vlasceanu
> <[e-mail]>; [e-mail]
> 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 <[e-mail]>
> > > >
> > > > 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

Mimi Zohar April 24, 2020, 2:45 p.m. UTC | #5

On Fri, 2020-04-24 at 12:18 +0000, Roberto Sassu wrote:

> > 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 <[e-mail]>
> > > > >
> > > > > 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

At least for this measurement list sample, there doesn't seem to be
any benefit to hashing the digest.  In terms of increasing the number
of slots, the additional memory is minimal and shouldn't negatively
affect small embedded devices.  Please make sure checkpatch doesn't
flag it.

thanks,

Mimi

Patch

diff --git a/security/integrity/ima/ima.h b/security/integrity/ima/ima.h
index 64317d95363e..cf0022c2bc14 100644
--- a/security/integrity/ima/ima.h
+++ b/security/integrity/ima/ima.h
@@ -177,7 +177,7 @@  extern struct ima_h_table ima_htable;
 
 static inline unsigned long ima_hash_key(u8 *digest)
 {
-	return hash_long(*digest, IMA_HASH_BITS);
+	return hash_long(*((unsigned long *)digest), IMA_HASH_BITS);
 }
 
 #define __ima_hooks(hook)		\