[PATCH v1 2/3] Mark functions with the latent_entropy attribute

[Emese Revfy]

These functions have been selected because they are init functions or
are called at random times or they have variable loops.

Based on work created by the PaX Team.

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---
block/blk-softirq.c | 2 +-
drivers/char/random.c | 6 +++---
fs/namespace.c | 2 +-
include/linux/compiler-gcc.h | 5 +++++
include/linux/compiler.h | 4 ++++
include/linux/fdtable.h | 2 +-
include/linux/genhd.h | 2 +-
include/linux/init.h | 10 ++++++++--
include/linux/random.h | 4 ++--
kernel/fork.c | 4 ++--
kernel/rcu/tiny.c | 2 +-
kernel/rcu/tree.c | 2 +-
kernel/sched/fair.c | 2 +-
kernel/softirq.c | 4 ++--
kernel/time/timer.c | 2 +-
lib/irq_poll.c | 2 +-
lib/random32.c | 2 +-
mm/page_alloc.c | 2 +-
net/core/dev.c | 4 ++--
19 files changed, 39 insertions(+), 24 deletions(-)

diff --git a/block/blk-softirq.c b/block/blk-softirq.c
index 53b1737..489eab8 100644
--- a/block/blk-softirq.c
+++ b/block/blk-softirq.c
@@ -18,7 +18,7 @@ static DEFINE_PER_CPU(struct list_head, blk_cpu_done);
* Softirq action handler - move entries to local list and loop over them
* while passing them to the queue registered handler.
*/
-static void blk_done_softirq(struct softirq_action *h)
+static __latent_entropy void blk_done_softirq(struct softirq_action *h)
{
struct list_head *cpu_list, local_list;

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 0158d3b..6cca3ed 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -443,9 +443,9 @@ struct entropy_store {
};

static void push_to_pool(struct work_struct *work);
-static __u32 input_pool_data[INPUT_POOL_WORDS];
-static __u32 blocking_pool_data[OUTPUT_POOL_WORDS];
-static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS];
+static __u32 input_pool_data[INPUT_POOL_WORDS] __latent_entropy;
+static __u32 blocking_pool_data[OUTPUT_POOL_WORDS] __latent_entropy;
+static __u32 nonblocking_pool_data[OUTPUT_POOL_WORDS] __latent_entropy;

static struct entropy_store input_pool = {
.poolinfo = &poolinfo_table[0],
diff --git a/fs/namespace.c b/fs/namespace.c
index 4fb1691..eed930c 100644
--- a/fs/namespace.c
+++ b/fs/namespace.c
@@ -2778,7 +2778,7 @@ static struct mnt_namespace *alloc_mnt_ns(struct user_namespace *user_ns)
return new_ns;
}

-struct mnt_namespace *copy_mnt_ns(unsigned long flags, struct mnt_namespace *ns,
+__latent_entropy struct mnt_namespace *copy_mnt_ns(unsigned long flags, struct mnt_namespace *ns,
struct user_namespace *user_ns, struct fs_struct *new_fs)
{
struct mnt_namespace *new_ns;
diff --git a/include/linux/compiler-gcc.h b/include/linux/compiler-gcc.h
index e294939..8d85907 100644
--- a/include/linux/compiler-gcc.h
+++ b/include/linux/compiler-gcc.h
@@ -188,6 +188,11 @@
#endif /* GCC_VERSION >= 40300 */

#if GCC_VERSION >= 40500
+
+#ifdef LATENT_ENTROPY_PLUGIN
+#define __latent_entropy __attribute__((latent_entropy))
+#endif
+
/*
* Mark a position in code as unreachable. This can be used to
* suppress control flow warnings after asm blocks that transfer
diff --git a/include/linux/compiler.h b/include/linux/compiler.h
index 793c082..c65327b 100644
--- a/include/linux/compiler.h
+++ b/include/linux/compiler.h
@@ -425,6 +425,10 @@ static __always_inline void __write_once_size(volatile void *p, void *res, int s
# define __attribute_const__ /* unimplemented */
#endif

+#ifndef __latent_entropy
+# define __latent_entropy
+#endif
+
/*
* Tell gcc if a function is cold. The compiler will assume any path
* directly leading to the call is unlikely.
diff --git a/include/linux/fdtable.h b/include/linux/fdtable.h
index 5295535..9852c7e 100644
--- a/include/linux/fdtable.h
+++ b/include/linux/fdtable.h
@@ -105,7 +105,7 @@ struct files_struct *get_files_struct(struct task_struct *);
void put_files_struct(struct files_struct *fs);
void reset_files_struct(struct files_struct *);
int unshare_files(struct files_struct **);
-struct files_struct *dup_fd(struct files_struct *, int *);
+struct files_struct *dup_fd(struct files_struct *, int *) __latent_entropy;
void do_close_on_exec(struct files_struct *);
int iterate_fd(struct files_struct *, unsigned,
int (*)(const void *, struct file *, unsigned),
diff --git a/include/linux/genhd.h b/include/linux/genhd.h
index 359a8e4..8736c1f 100644
--- a/include/linux/genhd.h
+++ b/include/linux/genhd.h
@@ -433,7 +433,7 @@ extern void disk_flush_events(struct gendisk *disk, unsigned int mask);
extern unsigned int disk_clear_events(struct gendisk *disk, unsigned int mask);

/* drivers/char/random.c */
-extern void add_disk_randomness(struct gendisk *disk);
+extern void add_disk_randomness(struct gendisk *disk) __latent_entropy;
extern void rand_initialize_disk(struct gendisk *disk);

static inline sector_t get_start_sect(struct block_device *bdev)
diff --git a/include/linux/init.h b/include/linux/init.h
index aedb254..68df2c3 100644
--- a/include/linux/init.h
+++ b/include/linux/init.h
@@ -37,9 +37,15 @@
* section.
*/

+#ifdef CONFIG_MEMORY_HOTPLUG
+#define add_meminit_latent_entropy
+#else
+#define add_meminit_latent_entropy __latent_entropy
+#endif
+
/* These are for everybody (although not all archs will actually
discard it in modules) */
-#define __init __section(.init.text) __cold notrace
+#define __init __section(.init.text) __cold notrace __latent_entropy
#define __initdata __section(.init.data)
#define __initconst __constsection(.init.rodata)
#define __exitdata __section(.exit.data)
@@ -92,7 +98,7 @@
#define __exit __section(.exit.text) __exitused __cold notrace

/* Used for MEMORY_HOTPLUG */
-#define __meminit __section(.meminit.text) __cold notrace
+#define __meminit __section(.meminit.text) __cold notrace add_meminit_latent_entropy
#define __meminitdata __section(.meminit.data)
#define __meminitconst __constsection(.meminit.rodata)
#define __memexit __section(.memexit.text) __exitused __cold notrace
diff --git a/include/linux/random.h b/include/linux/random.h
index 379f4bc..9fb07d1 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -27,8 +27,8 @@ static inline void add_latent_entropy(void)
}

extern void add_input_randomness(unsigned int type, unsigned int code,
- unsigned int value);
-extern void add_interrupt_randomness(int irq, int irq_flags);
+ unsigned int value) __latent_entropy;
+extern void add_interrupt_randomness(int irq, int irq_flags) __latent_entropy;

extern void get_random_bytes(void *buf, int nbytes);
extern int add_random_ready_callback(struct random_ready_callback *rdy);
diff --git a/kernel/fork.c b/kernel/fork.c
index d07d5a6..9fba65c 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -406,7 +406,7 @@ free_tsk:
}

#ifdef CONFIG_MMU
-static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)
+static __latent_entropy int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)
{
struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
struct rb_node **rb_link, *rb_parent;
@@ -1281,7 +1281,7 @@ init_task_pid(struct task_struct *task, enum pid_type type, struct pid *pid)
* parts of the process environment (as per the clone
* flags). The actual kick-off is left to the caller.
*/
-static struct task_struct *copy_process(unsigned long clone_flags,
+static __latent_entropy struct task_struct *copy_process(unsigned long clone_flags,
unsigned long stack_start,
unsigned long stack_size,
int __user *child_tidptr,
diff --git a/kernel/rcu/tiny.c b/kernel/rcu/tiny.c
index 944b1b4..1898559 100644
--- a/kernel/rcu/tiny.c
+++ b/kernel/rcu/tiny.c
@@ -170,7 +170,7 @@ static void __rcu_process_callbacks(struct rcu_ctrlblk *rcp)
false));
}

-static void rcu_process_callbacks(struct softirq_action *unused)
+static __latent_entropy void rcu_process_callbacks(struct softirq_action *unused)
{
__rcu_process_callbacks(&rcu_sched_ctrlblk);
__rcu_process_callbacks(&rcu_bh_ctrlblk);
diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index c7f1bc4..8821fce 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -3004,7 +3004,7 @@ __rcu_process_callbacks(struct rcu_state *rsp)
/*
* Do RCU core processing for the current CPU.
*/
-static void rcu_process_callbacks(struct softirq_action *unused)
+static __latent_entropy void rcu_process_callbacks(struct softirq_action *unused)
{
struct rcu_state *rsp;

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 218f8e8..cd745c2 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8205,7 +8205,7 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) { }
* run_rebalance_domains is triggered when needed from the scheduler tick.
* Also triggered for nohz idle balancing (with nohz_balancing_kick set).
*/
-static void run_rebalance_domains(struct softirq_action *h)
+static __latent_entropy void run_rebalance_domains(struct softirq_action *h)
{
struct rq *this_rq = this_rq();
enum cpu_idle_type idle = this_rq->idle_balance ?
diff --git a/kernel/softirq.c b/kernel/softirq.c
index 17caf4b..34033fd 100644
--- a/kernel/softirq.c
+++ b/kernel/softirq.c
@@ -482,7 +482,7 @@ void __tasklet_hi_schedule_first(struct tasklet_struct *t)
}
EXPORT_SYMBOL(__tasklet_hi_schedule_first);

-static void tasklet_action(struct softirq_action *a)
+static __latent_entropy void tasklet_action(struct softirq_action *a)
{
struct tasklet_struct *list;

@@ -518,7 +518,7 @@ static void tasklet_action(struct softirq_action *a)
}
}

-static void tasklet_hi_action(struct softirq_action *a)
+static __latent_entropy void tasklet_hi_action(struct softirq_action *a)
{
struct tasklet_struct *list;

diff --git a/kernel/time/timer.c b/kernel/time/timer.c
index 3a95f97..6008e7ae 100644
--- a/kernel/time/timer.c
+++ b/kernel/time/timer.c
@@ -1414,7 +1414,7 @@ void update_process_times(int user_tick)
/*
* This function runs timers and the timer-tq in bottom half context.
*/
-static void run_timer_softirq(struct softirq_action *h)
+static __latent_entropy void run_timer_softirq(struct softirq_action *h)
{
struct tvec_base *base = this_cpu_ptr(&tvec_bases);

diff --git a/lib/irq_poll.c b/lib/irq_poll.c
index 836f7db..63be749 100644
--- a/lib/irq_poll.c
+++ b/lib/irq_poll.c
@@ -74,7 +74,7 @@ void irq_poll_complete(struct irq_poll *iop)
}
EXPORT_SYMBOL(irq_poll_complete);

-static void irq_poll_softirq(struct softirq_action *h)
+static void __latent_entropy irq_poll_softirq(struct softirq_action *h)
{
struct list_head *list = this_cpu_ptr(&blk_cpu_iopoll);
int rearm = 0, budget = irq_poll_budget;
diff --git a/lib/random32.c b/lib/random32.c
index 510d1ce..722d2b6 100644
--- a/lib/random32.c
+++ b/lib/random32.c
@@ -47,7 +47,7 @@ static inline void prandom_state_selftest(void)
}
#endif

-static DEFINE_PER_CPU(struct rnd_state, net_rand_state);
+static DEFINE_PER_CPU(struct rnd_state, net_rand_state) __latent_entropy;

/**
* prandom_u32_state - seeded pseudo-random number generator.
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index d10324e..ffc4f4a 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1235,7 +1235,7 @@ static void __free_pages_ok(struct page *page, unsigned int order)
}

#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
-volatile u64 latent_entropy;
+volatile u64 latent_entropy __latent_entropy;
EXPORT_SYMBOL(latent_entropy);
#endif

diff --git a/net/core/dev.c b/net/core/dev.c
index 904ff43..723d3af 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -3851,7 +3851,7 @@ int netif_rx_ni(struct sk_buff *skb)
}
EXPORT_SYMBOL(netif_rx_ni);

-static void net_tx_action(struct softirq_action *h)
+static __latent_entropy void net_tx_action(struct softirq_action *h)
{
struct softnet_data *sd = this_cpu_ptr(&softnet_data);

@@ -5175,7 +5175,7 @@ out_unlock:
return work;
}

-static void net_rx_action(struct softirq_action *h)
+static __latent_entropy void net_rx_action(struct softirq_action *h)
{
struct softnet_data *sd = this_cpu_ptr(&softnet_data);
unsigned long time_limit = jiffies + 2;
--
2.8.1

[Emese Revfy]

I would like to introduce the latent_entropy gcc plugin. This plugin mitigates
the problem of the kernel having too little entropy during and after boot
for generating crypto keys.

This plugin mixes random values into the latent_entropy global variable
in functions marked by the __latent_entropy attribute.
The value of this global variable is added to the kernel entropy pool
to increase the entropy.

It is a CII project supported by the Linux Foundation.

The latent_entropy plugin was ported from grsecurity/PaX originally written by
the PaX Team. You can find more about the plugin here:
https://grsecurity.net/pipermail/grsecurity/2012-July/001093.html

The plugin supports all gcc version from 4.5 to 6.0.

I do some changes above the PaX version. The important one is mixing
the stack pointer into the global variable too.
You can find more about the changes here:
https://github.com/ephox-gcc-plugins/latent_entropy

This patch set is based on the "Introduce GCC plugin infrastructure" patch set (v9).

Emese Revfy (3):
Add the latent_entropy gcc plugin
Mark functions with the latent_entropy attribute
Add the extra_latent_entropy kernel parameter

---
Documentation/kernel-parameters.txt | 5 +
arch/Kconfig | 22 ++
arch/powerpc/kernel/Makefile | 8 +-
block/blk-softirq.c | 2 +-
drivers/char/random.c | 6 +-

fs/namespace.c | 2 +-
include/linux/compiler-gcc.h | 5 +

include/linux/compiler.h | 4 +

include/linux/fdtable.h | 2 +-
include/linux/genhd.h | 2 +-

include/linux/init.h | 10 +-
include/linux/random.h | 12 +-
init/main.c | 1 +
kernel/fork.c | 5 +-

kernel/rcu/tiny.c | 2 +-
kernel/rcu/tree.c | 2 +-
kernel/sched/fair.c | 2 +-

kernel/softirq.c | 4 +-

kernel/time/timer.c | 2 +-
lib/irq_poll.c | 2 +-
lib/random32.c | 2 +-

mm/page_alloc.c | 28 ++
net/core/dev.c | 4 +-
scripts/Makefile.gcc-plugins | 10 +-
scripts/gcc-plugins/Makefile | 1 +
scripts/gcc-plugins/latent_entropy_plugin.c | 446 ++++++++++++++++++++++++++++
26 files changed, 562 insertions(+), 29 deletions(-)

[Emese Revfy]

When extra_latent_entropy is passed on the kernel command line,
entropy will be extracted from up to the first 4GB of RAM while the
runtime memory allocator is being initialized.

Based on work created by the PaX Team.

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

Documentation/kernel-parameters.txt | 5 +++++
arch/Kconfig | 5 +++++
mm/page_alloc.c | 23 +++++++++++++++++++++++
3 files changed, 33 insertions(+)

diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt
index 5349363..6c2496e 100644
--- a/Documentation/kernel-parameters.txt
+++ b/Documentation/kernel-parameters.txt
@@ -2862,6 +2862,11 @@ bytes respectively. Such letter suffixes can also be entirely omitted.
the specified number of seconds. This is to be used if
your oopses keep scrolling off the screen.

+ extra_latent_entropy
+ Enable a very simple form of latent entropy extraction
+ from the first 4GB of memory as the bootmem allocator
+ passes the memory pages to the buddy allocator.
+
pcbit= [HW,ISDN]

pcd. [PARIDE]
diff --git a/arch/Kconfig b/arch/Kconfig
index 74489df..327d1e4 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -403,6 +403,11 @@ config GCC_PLUGIN_LATENT_ENTROPY
there is little 'natural' source of entropy normally. The cost
is some slowdown of the boot process and fork and irq processing.

+ When extra_latent_entropy is passed on the kernel command line,
+ entropy will be extracted from up to the first 4GB of RAM while the
+ runtime memory allocator is being initialized. This costs even more
+ slowdown of the boot process.
+
Note that entropy extracted this way is not known to be cryptographically
secure!

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index ffc4f4a..c79407b 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -63,6 +63,7 @@
#include <linux/sched/rt.h>
#include <linux/page_owner.h>
#include <linux/kthread.h>
+#include <linux/random.h>

#include <asm/sections.h>
#include <asm/tlbflush.h>
@@ -1235,6 +1236,15 @@ static void __free_pages_ok(struct page *page, unsigned int order)
}

#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
+bool __meminitdata extra_latent_entropy;
+
+static int __init setup_extra_latent_entropy(char *str)
+{
+ extra_latent_entropy = true;
+ return 0;
+}
+early_param("extra_latent_entropy", setup_extra_latent_entropy);
+

volatile u64 latent_entropy __latent_entropy;
EXPORT_SYMBOL(latent_entropy);
#endif

@@ -1254,6 +1264,19 @@ static void __init __free_pages_boot_core(struct page *page, unsigned int order)
__ClearPageReserved(p);
set_page_count(p, 0);

+#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
+ if (extra_latent_entropy && !PageHighMem(page) && page_to_pfn(page) < 0x100000) {
+ u64 hash = 0;
+ size_t index, end = PAGE_SIZE * nr_pages / sizeof hash;
+ const u64 *data = lowmem_page_address(page);
+
+ for (index = 0; index < end; index++)
+ hash ^= hash + data[index];
+ latent_entropy ^= hash;
+ add_device_randomness((const void *)&latent_entropy, sizeof(latent_entropy));
+ }
+#endif
+
page_zone(page)->managed_pages += nr_pages;
set_page_refcounted(page);
__free_pages(page, order);
--
2.8.1

[Kees Cook]

We try to minimize #ifdefs in the .c code, so in this case, I think I
would define "extra_latent_entropy" during an #else above so this "if"
can be culled by the compiler automatically:

#else
# define extra_latent_entropy false
#endif

Others may have better suggestions to avoid the second #ifdef, but
this seems the cleanest way to me to tie this to the earlier #ifdef.

-Kees

> page_zone(page)->managed_pages += nr_pages;
> set_page_refcounted(page);
> __free_pages(page, order);
> --
> 2.8.1
>

--
Kees Cook
Chrome OS & Brillo Security

[Kees Cook]

On Mon, May 23, 2016 at 3:16 PM, Emese Revfy <re.e...@gmail.com> wrote:
> These functions have been selected because they are init functions or
> are called at random times or they have variable loops.
>
> Based on work created by the PaX Team.
>
> Signed-off-by: Emese Revfy <re.e...@gmail.com>

> [...]

> --- a/include/linux/compiler-gcc.h
> +++ b/include/linux/compiler-gcc.h
> @@ -188,6 +188,11 @@
> #endif /* GCC_VERSION >= 40300 */
>
> #if GCC_VERSION >= 40500
> +
> +#ifdef LATENT_ENTROPY_PLUGIN
> +#define __latent_entropy __attribute__((latent_entropy))
> +#endif

This deserves a full comment above it to describe its purpose and use
for when people go trying to figure out what it is and where to use
it. The commit message is a bit terse, so I'd try to expand both to
describe what function characteristics a developer should look for to
mark something with __latent_entropy.

> +
> /*
> * Mark a position in code as unreachable. This can be used to
> * suppress control flow warnings after asm blocks that transfer

> [...]

I was confused by these defines. :) Maybe "add_meminit_latent_entropy"
should be named "__memory_hotplug_only_latent_entropy" or something
like that?

-Kees

[Emese Revfy]

Hi,

I think the best way would be if I removed all #ifdefs because
this is useful without the latent_entropy plugin.
I don't know wether the default value of extra_latent_entropy
should be true or false. I'll do some performance measurements.

--
Emese

[Emese Revfy]

I think the plugin doesn't cause a significant slowdown when CONFIG_MEMORY_HOTPLUG is enabled so I would rather always add the __latent_entropy attribute to __meminit.

--
Emese

[Kees Cook]

That seems fine to me. :)

[Emese Revfy]

The latent_entropy gcc attribute can be only on functions and variables.
If it is on a function then the plugin will instrument it. If the attribute
is on a variable then the plugin will initialize it with a random value.
The variable must be an integer, an integer array type or a structure with integer fields.

These functions have been selected because they are init functions or
are called at random times or they have variable loops.

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

block/blk-softirq.c | 2 +-
drivers/char/random.c | 6 +++---
fs/namespace.c | 2 +-
include/linux/compiler-gcc.h | 5 +++++
include/linux/compiler.h | 4 ++++

include/linux/fdtable.h | 2 +-
include/linux/genhd.h | 2 +-

include/linux/init.h | 4 ++--

include/linux/random.h | 4 ++--
kernel/fork.c | 4 ++--

kernel/rcu/tiny.c | 2 +-
kernel/rcu/tree.c | 2 +-
kernel/sched/fair.c | 2 +-

kernel/softirq.c | 4 ++--

kernel/time/timer.c | 2 +-
lib/irq_poll.c | 2 +-
lib/random32.c | 2 +-

mm/page_alloc.c | 2 +-
net/core/dev.c | 4 ++--

19 files changed, 33 insertions(+), 24 deletions(-)

--- a/include/linux/compiler-gcc.h
+++ b/include/linux/compiler-gcc.h
@@ -188,6 +188,11 @@
#endif /* GCC_VERSION >= 40300 */

#if GCC_VERSION >= 40500
+
+#ifdef LATENT_ENTROPY_PLUGIN
+#define __latent_entropy __attribute__((latent_entropy))
+#endif

+
/*
* Mark a position in code as unreachable. This can be used to
* suppress control flow warnings after asm blocks that transfer

diff --git a/include/linux/init.h b/include/linux/init.h
index aedb254..8bbc9f4 100644
--- a/include/linux/init.h
+++ b/include/linux/init.h
@@ -39,7 +39,7 @@

/* These are for everybody (although not all archs will actually
discard it in modules) */
-#define __init __section(.init.text) __cold notrace
+#define __init __section(.init.text) __cold notrace __latent_entropy
#define __initdata __section(.init.data)
#define __initconst __constsection(.init.rodata)
#define __exitdata __section(.exit.data)

@@ -92,7 +92,7 @@

#define __exit __section(.exit.text) __exitused __cold notrace

/* Used for MEMORY_HOTPLUG */
-#define __meminit __section(.meminit.text) __cold notrace

+#define __meminit __section(.meminit.text) __cold notrace __latent_entropy

#define __meminitdata __section(.meminit.data)
#define __meminitconst __constsection(.meminit.rodata)
#define __memexit __section(.memexit.text) __exitused __cold notrace

diff --git a/include/linux/random.h b/include/linux/random.h
index 4ea73ee..0675393 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -29,8 +29,8 @@ static inline void add_latent_entropy(void) {}
#endif

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index d10324e..ffc4f4a 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1235,7 +1235,7 @@ static void __free_pages_ok(struct page *page, unsigned int order)
}

#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
-volatile u64 latent_entropy;
+volatile u64 latent_entropy __latent_entropy;
EXPORT_SYMBOL(latent_entropy);
#endif

[Emese Revfy]

When extra_latent_entropy is passed on the kernel command line,
entropy will be extracted from up to the first 4GB of RAM while the
runtime memory allocator is being initialized.

Based on work created by the PaX Team.

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

Documentation/kernel-parameters.txt | 5 +++++
arch/Kconfig | 5 +++++

mm/page_alloc.c | 25 +++++++++++++++++++++++++
3 files changed, 35 insertions(+)

diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt
index 5349363..6c2496e 100644
--- a/Documentation/kernel-parameters.txt
+++ b/Documentation/kernel-parameters.txt
@@ -2862,6 +2862,11 @@ bytes respectively. Such letter suffixes can also be entirely omitted.
the specified number of seconds. This is to be used if
your oopses keep scrolling off the screen.

+ extra_latent_entropy
+ Enable a very simple form of latent entropy extraction
+ from the first 4GB of memory as the bootmem allocator
+ passes the memory pages to the buddy allocator.
+
pcbit= [HW,ISDN]

pcd. [PARIDE]
diff --git a/arch/Kconfig b/arch/Kconfig

index 7115867..cbfa8d3 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -404,6 +404,11 @@ config GCC_PLUGIN_LATENT_ENTROPY
is some slowdown of the boot process (about 0.5%) and fork and

irq processing.

+ When extra_latent_entropy is passed on the kernel command line,
+ entropy will be extracted from up to the first 4GB of RAM while the
+ runtime memory allocator is being initialized. This costs even more
+ slowdown of the boot process.
+
Note that entropy extracted this way is not known to be cryptographically
secure!

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index ffc4f4a..72c61bd 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c

@@ -63,6 +63,7 @@
#include <linux/sched/rt.h>
#include <linux/page_owner.h>
#include <linux/kthread.h>
+#include <linux/random.h>

#include <asm/sections.h>
#include <asm/tlbflush.h>

@@ -1234,6 +1235,15 @@ static void __free_pages_ok(struct page *page, unsigned int order)
local_irq_restore(flags);

}

+bool __meminitdata extra_latent_entropy;
+
+static int __init setup_extra_latent_entropy(char *str)
+{
+ extra_latent_entropy = true;
+ return 0;
+}
+early_param("extra_latent_entropy", setup_extra_latent_entropy);
+

#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY

volatile u64 latent_entropy __latent_entropy;
EXPORT_SYMBOL(latent_entropy);

@@ -1254,6 +1264,21 @@ static void __init __free_pages_boot_core(struct page *page, unsigned int order)
__ClearPageReserved(p);
set_page_count(p, 0);

+ if (extra_latent_entropy && !PageHighMem(page) && page_to_pfn(page) < 0x100000) {
+ u64 hash = 0;
+ size_t index, end = PAGE_SIZE * nr_pages / sizeof hash;
+ const u64 *data = lowmem_page_address(page);
+
+ for (index = 0; index < end; index++)
+ hash ^= hash + data[index];

+#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY

+ latent_entropy ^= hash;
+ add_device_randomness((const void *)&latent_entropy, sizeof(latent_entropy));

+#else
+ add_device_randomness((const void *)&hash, sizeof(hash));
+#endif
+ }
+

[Emese Revfy]

I would like to introduce the latent_entropy gcc plugin. This plugin mitigates
the problem of the kernel having too little entropy during and after boot
for generating crypto keys.

This plugin mixes random values into the latent_entropy global variable
in functions marked by the __latent_entropy attribute.
The value of this global variable is added to the kernel entropy pool
to increase the entropy.

It is a CII project supported by the Linux Foundation.

The latent_entropy plugin was ported from grsecurity/PaX originally written by
the PaX Team. You can find more about the plugin here:
https://grsecurity.net/pipermail/grsecurity/2012-July/001093.html

The plugin supports all gcc version from 4.5 to 6.0.

I do some changes above the PaX version. The important one is mixing
the stack pointer into the global variable too.
You can find more about the changes here:
https://github.com/ephox-gcc-plugins/latent_entropy

This patch set is based on the "Introduce GCC plugin infrastructure" patch set (v9 next-20160520).

Emese Revfy (3):
Add the latent_entropy gcc plugin
Mark functions with the latent_entropy attribute
Add the extra_latent_entropy kernel parameter

Changes from v1:
* Remove unnecessary ifdefs
(Suggested-by: Kees Cook <kees...@chromium.org>)
* Separate the two definitions of add_latent_entropy()
(Suggested-by: Kees Cook <kees...@chromium.org>)
* Removed unnecessary global variable (latent_entropy_plugin.c)
* About the latent_entropy gcc attribute (latent_entropy_plugin.c)
* Measure the boot time performance impact of the latent_entropy plugin (arch/Kconfig)

---
Documentation/kernel-parameters.txt | 5 +
arch/Kconfig | 23 ++
arch/powerpc/kernel/Makefile | 8 +-
block/blk-softirq.c | 2 +-
drivers/char/random.c | 6 +-

fs/namespace.c | 2 +-
include/linux/compiler-gcc.h | 5 +

include/linux/compiler.h | 4 +

include/linux/fdtable.h | 2 +-
include/linux/genhd.h | 2 +-

include/linux/init.h | 4 +-
include/linux/random.h | 14 +-

init/main.c | 1 +
kernel/fork.c | 5 +-

kernel/rcu/tiny.c | 2 +-
kernel/rcu/tree.c | 2 +-
kernel/sched/fair.c | 2 +-

kernel/softirq.c | 4 +-

kernel/time/timer.c | 2 +-
lib/irq_poll.c | 2 +-
lib/random32.c | 2 +-

mm/page_alloc.c | 30 ++

net/core/dev.c | 4 +-
scripts/Makefile.gcc-plugins | 10 +-
scripts/gcc-plugins/Makefile | 1 +

scripts/gcc-plugins/latent_entropy_plugin.c | 454 ++++++++++++++++++++++++++++
26 files changed, 569 insertions(+), 29 deletions(-)

[Emese Revfy]

This plugin mitigates the problem of the kernel having too little entropy during
and after boot for generating crypto keys.

It creates a local variable in every marked function. The value of this variable is
modified by randomly chosen operations (add, xor and rol) and
random values (gcc generates them at compile time and the stack pointer at runtime).
It depends on the control flow (e.g., loops, conditions).

Before the function returns the plugin writes this local variable
into the latent_entropy global variable. The value of this global variable is
added to the kernel entropy pool in do_one_initcall() and _do_fork().

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

arch/Kconfig | 18 ++
arch/powerpc/kernel/Makefile | 8 +-
include/linux/random.h | 10 +
init/main.c | 1 +
kernel/fork.c | 1 +
mm/page_alloc.c | 5 +

scripts/Makefile.gcc-plugins | 10 +-
scripts/gcc-plugins/Makefile | 1 +
scripts/gcc-plugins/latent_entropy_plugin.c | 454 ++++++++++++++++++++++++++++

9 files changed, 502 insertions(+), 6 deletions(-)
create mode 100644 scripts/gcc-plugins/latent_entropy_plugin.c

diff --git a/arch/Kconfig b/arch/Kconfig
index 5feadad..7115867 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -393,6 +393,24 @@ config GCC_PLUGIN_SANCOV
gcc-4.5 on). It is based on the commit "Add fuzzing coverage support"
by Dmitry Vyukov <dvy...@google.com>.

+config GCC_PLUGIN_LATENT_ENTROPY
+ bool "Generate some entropy during boot and runtime"
+ depends on GCC_PLUGINS
+ help
+ By saying Y here the kernel will instrument some kernel code to
+ extract some entropy from both original and artificially created
+ program state. This will help especially embedded systems where
+ there is little 'natural' source of entropy normally. The cost
+ is some slowdown of the boot process (about 0.5%) and fork and
+ irq processing.
+

+ Note that entropy extracted this way is not known to be cryptographically

+ secure!
+
+ This plugin was ported from grsecurity/PaX. More information at:
+ * https://grsecurity.net/
+ * https://pax.grsecurity.net/
+
config HAVE_CC_STACKPROTECTOR
bool
help
diff --git a/arch/powerpc/kernel/Makefile b/arch/powerpc/kernel/Makefile
index 2da380f..6c7e448 100644
--- a/arch/powerpc/kernel/Makefile
+++ b/arch/powerpc/kernel/Makefile
@@ -16,10 +16,10 @@ endif

ifdef CONFIG_FUNCTION_TRACER
# Do not trace early boot code
-CFLAGS_REMOVE_cputable.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
-CFLAGS_REMOVE_prom_init.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
-CFLAGS_REMOVE_btext.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
-CFLAGS_REMOVE_prom.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
+CFLAGS_REMOVE_cputable.o = -mno-sched-epilog $(CC_FLAGS_FTRACE) $(DISABLE_LATENT_ENTROPY_PLUGIN)
+CFLAGS_REMOVE_prom_init.o = -mno-sched-epilog $(CC_FLAGS_FTRACE) $(DISABLE_LATENT_ENTROPY_PLUGIN)
+CFLAGS_REMOVE_btext.o = -mno-sched-epilog $(CC_FLAGS_FTRACE) $(DISABLE_LATENT_ENTROPY_PLUGIN)
+CFLAGS_REMOVE_prom.o = -mno-sched-epilog $(CC_FLAGS_FTRACE) $(DISABLE_LATENT_ENTROPY_PLUGIN)
# do not trace tracer code
CFLAGS_REMOVE_ftrace.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
# timers used by tracing
diff --git a/include/linux/random.h b/include/linux/random.h
index e47e533..4ea73ee 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -18,6 +18,16 @@ struct random_ready_callback {
};

extern void add_device_randomness(const void *, unsigned int);
+
+#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
+static inline void add_latent_entropy(void)
+{

+ add_device_randomness((const void *)&latent_entropy, sizeof(latent_entropy));
+}

+#else
+static inline void add_latent_entropy(void) {}
+#endif
+

extern void add_input_randomness(unsigned int type, unsigned int code,

unsigned int value);

extern void add_interrupt_randomness(int irq, int irq_flags);

diff --git a/init/main.c b/init/main.c
index 4c17fda..07e4174 100644
--- a/init/main.c
+++ b/init/main.c
@@ -781,6 +781,7 @@ int __init_or_module do_one_initcall(initcall_t fn)
}
WARN(msgbuf[0], "initcall %pF returned with %s\n", fn, msgbuf);

+ add_latent_entropy();
return ret;
}

diff --git a/kernel/fork.c b/kernel/fork.c
index cdf520f..d07d5a6 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1766,6 +1766,7 @@ long _do_fork(unsigned long clone_flags,

p = copy_process(clone_flags, stack_start, stack_size,
child_tidptr, NULL, trace, tls, NUMA_NO_NODE);
+ add_latent_entropy();
/*
* Do this prior waking up the new thread - the thread pointer
* might get invalid after that point, if the thread exits quickly.
diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index f8f3bfc..d10324e 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -1234,6 +1234,11 @@ static void __free_pages_ok(struct page *page, unsigned int order)
local_irq_restore(flags);
}

+#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
+volatile u64 latent_entropy;
+EXPORT_SYMBOL(latent_entropy);
+#endif
+

static void __init __free_pages_boot_core(struct page *page, unsigned int order)

{
unsigned int nr_pages = 1 << order;
diff --git a/scripts/Makefile.gcc-plugins b/scripts/Makefile.gcc-plugins
index 5e22b60..cd7902c 100644
--- a/scripts/Makefile.gcc-plugins
+++ b/scripts/Makefile.gcc-plugins
@@ -6,6 +6,12 @@ ifdef CONFIG_GCC_PLUGINS

gcc-plugin-$(CONFIG_GCC_PLUGIN_CYC_COMPLEXITY) += cyc_complexity_plugin.so

+ gcc-plugin-$(CONFIG_GCC_PLUGIN_LATENT_ENTROPY) += latent_entropy_plugin.so
+ gcc-plugin-cflags-$(CONFIG_GCC_PLUGIN_LATENT_ENTROPY) += -DLATENT_ENTROPY_PLUGIN
+ ifdef CONFIG_PAX_LATENT_ENTROPY
+ DISABLE_LATENT_ENTROPY_PLUGIN += -fplugin-arg-latent_entropy_plugin-disable
+ endif
+
ifdef CONFIG_GCC_PLUGIN_SANCOV
ifeq ($(CFLAGS_KCOV),)
# It is needed because of the gcc-plugin.sh and gcc version checks.
@@ -19,9 +25,9 @@ ifdef CONFIG_GCC_PLUGINS
endif
endif

- GCC_PLUGINS_CFLAGS := $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y))
+ GCC_PLUGINS_CFLAGS := $(strip $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y)) $(gcc-plugin-cflags-y))

- export PLUGINCC GCC_PLUGINS_CFLAGS GCC_PLUGIN SANCOV_PLUGIN
+ export PLUGINCC GCC_PLUGINS_CFLAGS GCC_PLUGIN SANCOV_PLUGIN DISABLE_LATENT_ENTROPY_PLUGIN

ifeq ($(PLUGINCC),)
ifneq ($(GCC_PLUGINS_CFLAGS),)
diff --git a/scripts/gcc-plugins/Makefile b/scripts/gcc-plugins/Makefile
index 88c8ec4..a3f8ca4a 100644
--- a/scripts/gcc-plugins/Makefile
+++ b/scripts/gcc-plugins/Makefile
@@ -23,5 +23,6 @@ always := $($(HOSTLIBS)-y)

cyc_complexity_plugin-objs := cyc_complexity_plugin.o
sancov_plugin-objs := sancov_plugin.o
+latent_entropy_plugin-objs := latent_entropy_plugin.o

clean-files += *.so
diff --git a/scripts/gcc-plugins/latent_entropy_plugin.c b/scripts/gcc-plugins/latent_entropy_plugin.c
new file mode 100644
index 0000000..f606caa
--- /dev/null
+++ b/scripts/gcc-plugins/latent_entropy_plugin.c
@@ -0,0 +1,454 @@
+/*
+ * Copyright 2012-2016 by the PaX Team <page...@freemail.hu>
+ * Copyright 2016 by Emese Revfy <re.e...@gmail.com>
+ * Licensed under the GPL v2
+ *
+ * Note: the choice of the license means that the compilation process is
+ * NOT 'eligible' as defined by gcc's library exception to the GPL v3,
+ * but for the kernel it doesn't matter since it doesn't link against
+ * any of the gcc libraries
+ *
+ * gcc plugin to help generate a little bit of entropy from program state,
+ * used throughout the uptime of the kernel
+ *
+ * TODO:
+ * - add ipa pass to identify not explicitly marked candidate functions
+ * - mix in more program state (function arguments/return values, loop variables, etc)
+ * - more instrumentation control via attribute parameters
+ *
+ * BUGS:
+ * - none known
+ *
+ * Options:
+ * -fplugin-arg-latent_entropy_plugin-disable
+ *
+ * Attribute: __attribute__((latent_entropy))
+ * The latent_entropy gcc attribute can be only on functions and variables.
+ * If it is on a function then the plugin will instrument it. If the attribute
+ * is on a variable then the plugin will initialize it with a random value.
+ * The variable must be an integer, an integer array type or a structure with integer fields.
+ */
+
+#include "gcc-common.h"
+
+int plugin_is_GPL_compatible;
+
+static GTY(()) tree latent_entropy_decl;
+
+static struct plugin_info latent_entropy_plugin_info = {
+ .version = "201605292100",
+ .help = "disable\tturn off latent entropy instrumentation\n",
+};
+
+static unsigned HOST_WIDE_INT seed;
+static unsigned HOST_WIDE_INT get_random_const(void)
+{
+ unsigned int i;
+ unsigned HOST_WIDE_INT ret = 0;
+
+ for (i = 0; i < 8 * sizeof ret; i++) {
+ ret = (ret << 1) | (seed & 1);
+ seed >>= 1;
+ if (ret & 1)
+ seed ^= 0xD800000000000000ULL;
+ }
+
+ return ret;
+}
+
+static tree handle_latent_entropy_attribute(tree *node, tree name, tree args __unused, int flags __unused, bool *no_add_attrs)
+{
+ tree type;
+ unsigned long long mask;
+#if BUILDING_GCC_VERSION <= 4007
+ VEC(constructor_elt, gc) *vals;
+#else
+ vec<constructor_elt, va_gc> *vals;
+#endif
+
+ switch (TREE_CODE(*node)) {
+ default:
+ *no_add_attrs = true;
+ error("%qE attribute only applies to functions and variables", name);
+ break;
+
+ case VAR_DECL:
+ if (DECL_INITIAL(*node)) {
+ *no_add_attrs = true;
+ error("variable %qD with %qE attribute must not be initialized", *node, name);
+ break;
+ }
+
+ if (!TREE_STATIC(*node)) {
+ *no_add_attrs = true;
+ error("variable %qD with %qE attribute must not be local", *node, name);
+ break;
+ }
+
+ type = TREE_TYPE(*node);
+ switch (TREE_CODE(type)) {
+ default:
+ *no_add_attrs = true;
+ error("variable %qD with %qE attribute must be an integer or a fixed length integer array type"
+ "or a fixed sized structure with integer fields", *node, name);
+ break;
+
+ case RECORD_TYPE: {
+ tree field;
+ unsigned int nelt = 0;
+
+ for (field = TYPE_FIELDS(type); field; nelt++, field = TREE_CHAIN(field)) {
+ tree fieldtype;
+
+ fieldtype = TREE_TYPE(field);
+ if (TREE_CODE(fieldtype) == INTEGER_TYPE)
+ continue;
+
+ *no_add_attrs = true;
+ error("structure variable %qD with %qE attribute has a non-integer field %qE", *node, name, field);
+ break;
+ }
+
+ if (field)
+ break;
+
+#if BUILDING_GCC_VERSION <= 4007
+ vals = VEC_alloc(constructor_elt, gc, nelt);
+#else
+ vec_alloc(vals, nelt);
+#endif
+
+ for (field = TYPE_FIELDS(type); field; field = TREE_CHAIN(field)) {
+ tree fieldtype;
+
+ fieldtype = TREE_TYPE(field);
+ mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(fieldtype)) - 1);
+ mask = 2 * (mask - 1) + 1;
+
+ if (TYPE_UNSIGNED(fieldtype))
+ CONSTRUCTOR_APPEND_ELT(vals, field, build_int_cstu(fieldtype, mask & get_random_const()));
+ else
+ CONSTRUCTOR_APPEND_ELT(vals, field, build_int_cst(fieldtype, mask & get_random_const()));
+ }
+
+ DECL_INITIAL(*node) = build_constructor(type, vals);
+ break;
+ }
+
+ case INTEGER_TYPE:
+ mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(type)) - 1);
+ mask = 2 * (mask - 1) + 1;
+
+ if (TYPE_UNSIGNED(type))
+ DECL_INITIAL(*node) = build_int_cstu(type, mask & get_random_const());
+ else
+ DECL_INITIAL(*node) = build_int_cst(type, mask & get_random_const());
+ break;
+
+ case ARRAY_TYPE: {
+ tree elt_type, array_size, elt_size;
+ unsigned int i, nelt;
+
+ elt_type = TREE_TYPE(type);
+ elt_size = TYPE_SIZE_UNIT(TREE_TYPE(type));
+ array_size = TYPE_SIZE_UNIT(type);
+
+ if (TREE_CODE(elt_type) != INTEGER_TYPE || !array_size || TREE_CODE(array_size) != INTEGER_CST) {
+ *no_add_attrs = true;
+ error("array variable %qD with %qE attribute must be a fixed length integer array type", *node, name);
+ break;
+ }
+
+ nelt = TREE_INT_CST_LOW(array_size) / TREE_INT_CST_LOW(elt_size);
+#if BUILDING_GCC_VERSION <= 4007
+ vals = VEC_alloc(constructor_elt, gc, nelt);
+#else
+ vec_alloc(vals, nelt);
+#endif
+
+ mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(elt_type)) - 1);
+ mask = 2 * (mask - 1) + 1;
+
+ for (i = 0; i < nelt; i++)
+ if (TYPE_UNSIGNED(elt_type))
+ CONSTRUCTOR_APPEND_ELT(vals, size_int(i), build_int_cstu(elt_type, mask & get_random_const()));
+ else
+ CONSTRUCTOR_APPEND_ELT(vals, size_int(i), build_int_cst(elt_type, mask & get_random_const()));
+
+ DECL_INITIAL(*node) = build_constructor(type, vals);
+ break;
+ }
+ }
+ break;
+
+ case FUNCTION_DECL:
+ break;
+ }
+
+ return NULL_TREE;
+}
+
+static struct attribute_spec latent_entropy_attr = {
+ .name = "latent_entropy",
+ .min_length = 0,
+ .max_length = 0,
+ .decl_required = true,
+ .type_required = false,
+ .function_type_required = false,
+ .handler = handle_latent_entropy_attribute,
+#if BUILDING_GCC_VERSION >= 4007
+ .affects_type_identity = false
+#endif
+};
+
+static void register_attributes(void *event_data __unused, void *data __unused)
+{
+ register_attribute(&latent_entropy_attr);
+}
+
+static bool latent_entropy_gate(void)
+{
+ /* don't bother with noreturn functions for now */
+ if (TREE_THIS_VOLATILE(current_function_decl))
+ return false;
+
+ /* gcc-4.5 doesn't discover some trivial noreturn functions */
+ if (EDGE_COUNT(EXIT_BLOCK_PTR_FOR_FN(cfun)->preds) == 0)
+ return false;
+
+ return lookup_attribute("latent_entropy", DECL_ATTRIBUTES(current_function_decl)) != NULL_TREE;
+}
+
+static tree create_a_tmp_var(tree type, const char *name)
+{
+ tree var;
+
+ var = create_tmp_var(type, name);
+ add_referenced_var(var);
+ mark_sym_for_renaming(var);
+ return var;
+}
+
+static enum tree_code get_op(tree *rhs)
+{
+ static enum tree_code op;
+ unsigned HOST_WIDE_INT random_const;
+
+ random_const = get_random_const();
+
+ switch (op) {
+ case BIT_XOR_EXPR:
+ op = PLUS_EXPR;
+ break;
+
+ case PLUS_EXPR:
+ if (rhs) {
+ op = LROTATE_EXPR;
+ random_const &= HOST_BITS_PER_WIDE_INT - 1;
+ break;
+ }
+
+ case LROTATE_EXPR:
+ default:
+ op = BIT_XOR_EXPR;
+ break;
+ }
+ if (rhs)
+ *rhs = build_int_cstu(unsigned_intDI_type_node, random_const);
+ return op;
+}
+
+static void perturb_local_entropy(basic_block bb, tree local_entropy)
+{
+ gimple_stmt_iterator gsi;
+ gimple assign;
+ tree rhs;
+ enum tree_code subcode;
+
+ subcode = get_op(&rhs);
+ assign = gimple_build_assign_with_ops(subcode, local_entropy, local_entropy, rhs);
+ gsi = gsi_after_labels(bb);
+ gsi_insert_before(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+}
+
+static void perturb_latent_entropy(basic_block bb, tree rhs)
+{
+ gimple_stmt_iterator gsi;
+ gimple assign;
+ tree temp;
+ enum tree_code subcode;
+
+ /* create temporary copy of latent_entropy */
+ temp = create_a_tmp_var(unsigned_intDI_type_node, "temp_latent_entropy");
+
+ gsi = gsi_last_bb(bb);
+
+ /* 1. read... */
+ add_referenced_var(latent_entropy_decl);
+ mark_sym_for_renaming(latent_entropy_decl);
+ assign = gimple_build_assign(temp, latent_entropy_decl);
+ gsi_insert_before(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+
+ /* 2. ...modify... */
+ subcode = get_op(NULL);
+ assign = gimple_build_assign_with_ops(subcode, temp, temp, rhs);
+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+
+ /* 3. ...write latent_entropy */
+ assign = gimple_build_assign(latent_entropy_decl, temp);
+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+}
+
+static void mix_in_sp(basic_block bb, tree local_entropy)
+{
+ gimple assign, call;
+ tree frame_addr, rand_const;
+ gimple_stmt_iterator gsi = gsi_after_labels(bb);
+
+ frame_addr = create_a_tmp_var(ptr_type_node, "local_entropy_frame_addr");
+
+ call = gimple_build_call(builtin_decl_implicit(BUILT_IN_FRAME_ADDRESS), 1, integer_zero_node);
+ gimple_call_set_lhs(call, frame_addr);
+ gsi_insert_before(&gsi, call, GSI_NEW_STMT);
+ update_stmt(call);
+
+ assign = gimple_build_assign(local_entropy, fold_convert(unsigned_intDI_type_node, frame_addr));
+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+
+ rand_const = build_int_cstu(unsigned_intDI_type_node, get_random_const());
+ assign = gimple_build_assign_with_ops(BIT_XOR_EXPR, local_entropy, local_entropy, rand_const);
+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+}
+
+static unsigned int latent_entropy_execute(void)
+{
+ basic_block bb;
+ tree local_entropy;
+
+ if (!latent_entropy_decl) {
+ varpool_node_ptr node;
+
+ FOR_EACH_VARIABLE(node) {
+ tree var = NODE_DECL(node);
+
+ if (DECL_NAME_LENGTH(var) < sizeof("latent_entropy") - 1)
+ continue;
+ if (strcmp(IDENTIFIER_POINTER(DECL_NAME(var)), "latent_entropy"))
+ continue;
+ latent_entropy_decl = var;
+ break;
+ }
+ if (!latent_entropy_decl)
+ return 0;
+ }
+
+ gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
+ bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
+ if (!single_pred_p(bb)) {
+ split_edge(single_succ_edge(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
+ gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
+ bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
+ }
+
+ /* create local entropy variable */
+ local_entropy = create_a_tmp_var(unsigned_intDI_type_node, "local_entropy");
+
+ /* 1. stack pointer */
+ mix_in_sp(bb, local_entropy);
+
+ bb = bb->next_bb;
+ /* 2. instrument each BB with an operation on the local entropy variable */
+ while (bb != EXIT_BLOCK_PTR_FOR_FN(cfun)) {
+ perturb_local_entropy(bb, local_entropy);
+ bb = bb->next_bb;
+ };
+
+ /* 3. mix local entropy into the global entropy variable */
+ gcc_assert(single_pred_p(EXIT_BLOCK_PTR_FOR_FN(cfun)));
+ perturb_latent_entropy(single_pred(EXIT_BLOCK_PTR_FOR_FN(cfun)), local_entropy);
+ return 0;
+}
+
+static void latent_entropy_start_unit(void *gcc_data __unused, void *user_data __unused)
+{
+ tree latent_entropy_type;
+
+ seed = get_random_seed(false);
+
+ if (in_lto_p)
+ return;
+
+ /* extern volatile u64 latent_entropy */
+ gcc_assert(TYPE_PRECISION(long_long_unsigned_type_node) == 64);
+ latent_entropy_type = build_qualified_type(long_long_unsigned_type_node, TYPE_QUALS(long_long_unsigned_type_node) | TYPE_QUAL_VOLATILE);
+ latent_entropy_decl = build_decl(UNKNOWN_LOCATION, VAR_DECL, get_identifier("latent_entropy"), latent_entropy_type);
+
+ TREE_STATIC(latent_entropy_decl) = 1;
+ TREE_PUBLIC(latent_entropy_decl) = 1;
+ TREE_USED(latent_entropy_decl) = 1;
+ DECL_PRESERVE_P(latent_entropy_decl) = 1;
+ TREE_THIS_VOLATILE(latent_entropy_decl) = 1;
+ DECL_EXTERNAL(latent_entropy_decl) = 1;
+ DECL_ARTIFICIAL(latent_entropy_decl) = 1;
+ lang_hooks.decls.pushdecl(latent_entropy_decl);
+}
+
+#define PASS_NAME latent_entropy
+#define PROPERTIES_REQUIRED PROP_gimple_leh | PROP_cfg
+#define TODO_FLAGS_FINISH TODO_verify_ssa | TODO_verify_stmts | TODO_dump_func | TODO_update_ssa
+#include "gcc-generate-gimple-pass.h"
+
+int plugin_init(struct plugin_name_args *plugin_info, struct plugin_gcc_version *version)
+{
+ bool enabled = true;
+ const char * const plugin_name = plugin_info->base_name;
+ const int argc = plugin_info->argc;
+ const struct plugin_argument * const argv = plugin_info->argv;
+ int i;
+
+ struct register_pass_info latent_entropy_pass_info;
+
+ latent_entropy_pass_info.pass = make_latent_entropy_pass();
+ latent_entropy_pass_info.reference_pass_name = "optimized";
+ latent_entropy_pass_info.ref_pass_instance_number = 1;
+ latent_entropy_pass_info.pos_op = PASS_POS_INSERT_BEFORE;
+ static const struct ggc_root_tab gt_ggc_r_gt_latent_entropy[] = {
+ {
+ .base = &latent_entropy_decl,
+ .nelt = 1,
+ .stride = sizeof(latent_entropy_decl),
+ .cb = &gt_ggc_mx_tree_node,
+ .pchw = &gt_pch_nx_tree_node
+ },
+ LAST_GGC_ROOT_TAB
+ };
+
+ if (!plugin_default_version_check(version, &gcc_version)) {
+ error(G_("incompatible gcc/plugin versions"));
+ return 1;
+ }
+
+ for (i = 0; i < argc; ++i) {
+ if (!(strcmp(argv[i].key, "disable"))) {
+ enabled = false;
+ continue;
+ }
+ error(G_("unkown option '-fplugin-arg-%s-%s'"), plugin_name, argv[i].key);
+ }
+
+ register_callback(plugin_name, PLUGIN_INFO, NULL, &latent_entropy_plugin_info);
+ if (enabled) {
+ register_callback(plugin_name, PLUGIN_START_UNIT, &latent_entropy_start_unit, NULL);
+ register_callback(plugin_name, PLUGIN_REGISTER_GGC_ROOTS, NULL, (void *)&gt_ggc_r_gt_latent_entropy);
+ register_callback(plugin_name, PLUGIN_PASS_MANAGER_SETUP, NULL, &latent_entropy_pass_info);
+ }
+ register_callback(plugin_name, PLUGIN_ATTRIBUTES, register_attributes, NULL);
+
+ return 0;
+}
--
2.8.1

[Andrew Morton]

On Tue, 31 May 2016 01:31:45 +0200 Emese Revfy <re.e...@gmail.com> wrote:

> This plugin mitigates the problem of the kernel having too little entropy during
> and after boot for generating crypto keys.
>
> It creates a local variable in every marked function. The value of this variable is
> modified by randomly chosen operations (add, xor and rol) and
> random values (gcc generates them at compile time and the stack pointer at runtime).
> It depends on the control flow (e.g., loops, conditions).
>
> Before the function returns the plugin writes this local variable
> into the latent_entropy global variable. The value of this global variable is
> added to the kernel entropy pool in do_one_initcall() and _do_fork().

I don't think I'm really understanding. Won't this produce the same
value on each and every boot?

[Emese Revfy]

No, because of interrupts and intentional data races.

--
Emese

[David Brown]

Wouldn't that result in the value having one of a small number of
values, then? Even if it was just one of thousands or millions of
values, it would make the search space quite small.

David

[Kees Cook]

My understanding is that it's not cryptographically secure, but it
provides a way for different machines and different boots to end up
with different seeds here, which is a big improvement over some of the
embedded devices that all boot with the same entropy every time.

I would, however, like to see the documentation improved to describe
the "How" and "Why". The "What" is pretty well covered. Adding
comments to the plugin for kernel developers (not compiler developers)
would help a lot: assume the reader knows nothing about gcc plugins.

[PaX Team]

what matters for latent entropy is not the actual values fed into the entropy
pool (they're effectively compile time constants save for runtime data dependent
computations) but the precise sequence of them. interrupts stir this sequence
and thus extract entropy. perhaps as a small example imagine that an uninterrupted
kernel boot sequence feeds these values into the entropy pool:
A B C

now imagine that a single interrupt can occur around any one of these values:
I A B C
A I B C
A B I C
A B C I

this way we can obtain 4 different final pool states that translate into up
to 2 bits of latent entropy (depends on how probable each sequence is). note
that this works regardless whether the underlying hardware has a high resolution
timer whose values the interrupt handler would feed into the pool.

the kernel boot process executes many of the above sequences with each sequence
potentially having a different length (the number of __init functions and initcalls
depends on the kernel config, initcalls execute for different lengths of time,
interrupt windows have different lengths, etc). how all this translates into
something measurable is a good question as i said elsewhere in the thread, my
completely unscientific guess would be that the number of interrupts is somehow
proportional to the extracted latent entropy.

cheers,
PaX Team

[Theodore Ts'o]

On Mon, Jun 06, 2016 at 09:30:12PM +0200, PaX Team wrote:
>
> what matters for latent entropy is not the actual values fed into the entropy
> pool (they're effectively compile time constants save for runtime data dependent
> computations) but the precise sequence of them. interrupts stir this sequence
> and thus extract entropy. perhaps as a small example imagine that an uninterrupted
> kernel boot sequence feeds these values into the entropy pool:
> A B C
>
> now imagine that a single interrupt can occur around any one of these values:
> I A B C
> A I B C
> A B I C
> A B C I
>
> this way we can obtain 4 different final pool states that translate into up
> to 2 bits of latent entropy (depends on how probable each sequence is). note
> that this works regardless whether the underlying hardware has a high resolution
> timer whose values the interrupt handler would feed into the pool.

Right, but if it's only about interrupts, we're doing this already
inside modern Linux kernels. On every single interrupt we are mixing
into a per-CPU "fast mix" pool the IP from the interrupt registers.

Since we're not claiming any additional entropy, I suppose it won't
hurt to do it twice, two different ways, but I'm not sure how much it
will actually help, and by doing the instrumentation in every single
basic block, instead of in the interrupt handler, I would think it
would be cheaper to do it in the interrupt handler.

- Ted

[PaX Team]

On 6 Jun 2016 at 19:13, Theodore Ts'o wrote:

> On Mon, Jun 06, 2016 at 09:30:12PM +0200, PaX Team wrote:
> >
> > what matters for latent entropy is not the actual values fed into the entropy
> > pool (they're effectively compile time constants save for runtime data dependent
> > computations) but the precise sequence of them. interrupts stir this sequence
> > and thus extract entropy. perhaps as a small example imagine that an uninterrupted
> > kernel boot sequence feeds these values into the entropy pool:
> > A B C
> >
> > now imagine that a single interrupt can occur around any one of these values:
> > I A B C
> > A I B C
> > A B I C
> > A B C I
> >
> > this way we can obtain 4 different final pool states that translate into up
> > to 2 bits of latent entropy (depends on how probable each sequence is). note
> > that this works regardless whether the underlying hardware has a high resolution
> > timer whose values the interrupt handler would feed into the pool.
>
> Right, but if it's only about interrupts,

(i believe that) latent entropy is found in more than just interrupt timing, there're
also data dependent computations that can have entropy, either on a single system or
across a population of them.

> we're doing this already inside modern Linux kernels. On every single
> interrupt we are mixing into a per-CPU "fast mix" pool the IP from the
> interrupt registers.

i agree that sampling the kernel register state can have entropy (the plugin
already extracts the current stack pointer) but i'm much less sure about
userland (at least i see no dependence on !user_mode(...)) since an attacker
could feed no entropy into the pool but still get it credited.

cheers,
PaX Team

[Theodore Ts'o]

On Tue, Jun 07, 2016 at 02:19:14PM +0200, PaX Team wrote:
> (i believe that) latent entropy is found in more than just interrupt timing, there're
> also data dependent computations that can have entropy, either on a single system or
> across a population of them.

It's not clear how much data dependent computations you would have in
kernel space that's not introduced by interrupts, but there would
some, I'm sure.

> > we're doing this already inside modern Linux kernels. On every single
> > interrupt we are mixing into a per-CPU "fast mix" pool the IP from the
> > interrupt registers.
>
> i agree that sampling the kernel register state can have entropy (the plugin
> already extracts the current stack pointer) but i'm much less sure about
> userland (at least i see no dependence on !user_mode(...)) since an attacker
> could feed no entropy into the pool but still get it credited.

Well, the attacker can't control when the interrupts happen, but it
could try to burn power by simply having a thread spin in an infinite
loop ("0: jmp 0"), sure. Of course, this would be rather noticeable,
and if there were any other jobs running, the attacker would be
degrading the amount of entropy that would be gathered, but not
eliminating it.

All of this goes into the question of how much entropy we can assume
can be gathered per interrupt (or in the case of basic block
instrumentation, per basic block). IIRC, in the latent_entropy
patches, the assumption is that zero entropy should be credited,
correct?

In the case Linux's current get_interrupt_randomness(), there's a
reason I'm using a very conservative 1/64th of a bit per interrupt.
In practice, on most modern CPU where we have a cycle counter, even if
the bad guy was doing a "0: jmp 0" spinning loop, we would still get
entropy via the cycle counter interacting with what is hopefully a
certain amount of entropy from the interrupt timing.

On a crappy $50 Android phone/tablet from China, using an ancient ARM
chip that doesn't have any cycle counting facilities, we're kind of
screwed, but those devices have lousy batteries, so if you have an
attacker that has disabled the wakelocks and is spinning in an
infinite loop, the battery life won't last long, so the problem will
mostly solve itself when the phone dies. :-)

- Ted

[PaX Team]

On 7 Jun 2016 at 9:58, Theodore Ts'o wrote:

> On Tue, Jun 07, 2016 at 02:19:14PM +0200, PaX Team wrote:
> > (i believe that) latent entropy is found in more than just interrupt timing, there're
> > also data dependent computations that can have entropy, either on a single system or
> > across a population of them.
>
> It's not clear how much data dependent computations you would have in
> kernel space that's not introduced by interrupts, but there would
> some, I'm sure.

there's plenty of such computations both during boot and later as well. starting
with kernel command line options through parsing firmware provided data to hardware
configurations to processing various queues, lists, trees, file systems, network
packets, etc. as for interrupts specifically, latent entropy can be extracted from
polled devices as well (e.g., i think even modern NICs can be turned into polling
mode under sufficient load as processing packets that way is more efficient).

> > i agree that sampling the kernel register state can have entropy (the plugin
> > already extracts the current stack pointer) but i'm much less sure about
> > userland (at least i see no dependence on !user_mode(...)) since an attacker
> > could feed no entropy into the pool but still get it credited.
>
> Well, the attacker can't control when the interrupts happen, but it
> could try to burn power by simply having a thread spin in an infinite
> loop ("0: jmp 0"), sure.

yes, that's one obvious way to accomplish it but even normal applications can
behave in a similar way, think about spinning event loops, media decoding, etc
whose sampled insn ptrs may provide less entropy than they get credited for.

> All of this goes into the question of how much entropy we can assume
> can be gathered per interrupt (or in the case of basic block
> instrumentation, per basic block). IIRC, in the latent_entropy
> patches, the assumption is that zero entropy should be credited,
> correct?

yes, no entropy is credited since i don't know how much there is and i tend to err
on the side of safety which means crediting 0 entropy for latent entropy. of course
the expectation is that it's not actually 0 but to prove any specific value or limit
is beyond my skills at least.

> In the case Linux's current get_interrupt_randomness(), there's a
> reason I'm using a very conservative 1/64th of a bit per interrupt.

i think it's not just per 64 interrupts but also after each elapsed second (i.e.,
whichever condition occurs first), so on an idle system (which i believe is more
likely to occur on exactly those small systems that the referenced paper was concerned
about) the credited entropy could be overestimated.

> In practice, on most modern CPU where we have a cycle counter,

a quick check for get_cycles shows that at least these archs seem to return 0:
arc, avr32, cris, frv, m32r, m68k, xtensa. now you may not think of them as modern,
but they're still used in real life devices. i think that latent entropy is still
an option on them.

cheers,
PaX Team

[Theodore Ts'o]

On Thu, Jun 09, 2016 at 07:22:29PM +0200, PaX Team wrote:
> > Well, the attacker can't control when the interrupts happen, but it
> > could try to burn power by simply having a thread spin in an infinite
> > loop ("0: jmp 0"), sure.
>
> yes, that's one obvious way to accomplish it but even normal applications can
> behave in a similar way, think about spinning event loops, media decoding, etc
> whose sampled insn ptrs may provide less entropy than they get credited for.

Sure, as long as we're assuming less than one bit of entropy per
interrupt, even for a loop which which is:

1: cmpl $1, -8(%rsp)
jz 1b

there would still be *some* uncertainty. And with an event loop there
would be more instructions to sample. Granted, the number of cycles
spent in each will be different, so there will be some biasing, but
that's one of the reason why we've been using 1/64 bit per interrupt.

> yes, no entropy is credited since i don't know how much there is and i tend to err
> on the side of safety which means crediting 0 entropy for latent entropy. of course
> the expectation is that it's not actually 0 but to prove any specific value or limit
> is beyond my skills at least.

Sure, that's fair.

> i think it's not just per 64 interrupts but also after each elapsed second (i.e.,
> whichever condition occurs first), so on an idle system (which i believe is more
> likely to occur on exactly those small systems that the referenced paper was concerned
> about) the credited entropy could be overestimated.

That's a fair concern. It might be that we should enforce some
minimum (at least 8 interrupts in all cases), but this is where it's
all about hueristics, especially on those systems that don't have random_get_entropy().

> > In practice, on most modern CPU where we have a cycle counter,
>
> a quick check for get_cycles shows that at least these archs seem to return 0:
> arc, avr32, cris, frv, m32r, m68k, xtensa. now you may not think of them as modern,
> but they're still used in real life devices. i think that latent entropy is still
> an option on them.

It's possible for a system not to have a cycle counter, but to have
something that can be used instead for random_get_entropy. That's
only being used for the m68k/amiga and mips/R6000[A] cases, but I keep
hoping that the archiecture maintainers for osme of these other
oddball platform (is that better than "non-modern"? :-) will come up
with something, but yes, it is those platforms where I've always been
the most worried. On the one hand, if the hardware is crap, there's
very little you can do. Unfortnuately, very often these crap
architectures have a very low BOM cost, so they are most likely to be
used in IOT devices. :-(

One could try to claim that these IOT devics won't have upgradeable
firmware and, so they'll probably be security disasters even without a
good random number generators, but oddly, that doesn't give me much
solace...

And in the end, that may be the strongest argment for the
latent_entropy plugin. Even if it doesn't provide a lot of extra
entropy, on those platforms we're going to be so starved of real
entropy that almost anything will be better than what we have today.

- Ted

[Kees Cook]

Yeah, that's been my thinking around this. And on more sane systems,
using latent_entropy doesn't make things worse. :)

[Kees Cook]

On Mon, May 30, 2016 at 4:31 PM, Emese Revfy <re.e...@gmail.com> wrote:
> This plugin mitigates the problem of the kernel having too little entropy during
> and after boot for generating crypto keys.
>
> It creates a local variable in every marked function. The value of this variable is
> modified by randomly chosen operations (add, xor and rol) and
> random values (gcc generates them at compile time and the stack pointer at runtime).
> It depends on the control flow (e.g., loops, conditions).
>
> Before the function returns the plugin writes this local variable
> into the latent_entropy global variable. The value of this global variable is
> added to the kernel entropy pool in do_one_initcall() and _do_fork().
>
> Signed-off-by: Emese Revfy <re.e...@gmail.com>

> [...]

> diff --git a/scripts/Makefile.gcc-plugins b/scripts/Makefile.gcc-plugins
> index 5e22b60..cd7902c 100644
> --- a/scripts/Makefile.gcc-plugins
> +++ b/scripts/Makefile.gcc-plugins
> @@ -6,6 +6,12 @@ ifdef CONFIG_GCC_PLUGINS
>
> gcc-plugin-$(CONFIG_GCC_PLUGIN_CYC_COMPLEXITY) += cyc_complexity_plugin.so
>
> + gcc-plugin-$(CONFIG_GCC_PLUGIN_LATENT_ENTROPY) += latent_entropy_plugin.so
> + gcc-plugin-cflags-$(CONFIG_GCC_PLUGIN_LATENT_ENTROPY) += -DLATENT_ENTROPY_PLUGIN
> + ifdef CONFIG_PAX_LATENT_ENTROPY
> + DISABLE_LATENT_ENTROPY_PLUGIN += -fplugin-arg-latent_entropy_plugin-disable
> + endif
> +
> ifdef CONFIG_GCC_PLUGIN_SANCOV
> ifeq ($(CFLAGS_KCOV),)
> # It is needed because of the gcc-plugin.sh and gcc version checks.
> @@ -19,9 +25,9 @@ ifdef CONFIG_GCC_PLUGINS
;> endif
> endif
>
> - GCC_PLUGINS_CFLAGS := $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y))
> + GCC_PLUGINS_CFLAGS := $(strip $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y)) $(gcc-plugin-cflags-y))

Is this change part of latent_entropy, or a general fix to the gcc
plugin infrastructure?

>
> - export PLUGINCC GCC_PLUGINS_CFLAGS GCC_PLUGIN SANCOV_PLUGIN
> + export PLUGINCC GCC_PLUGINS_CFLAGS GCC_PLUGIN SANCOV_PLUGIN DISABLE_LATENT_ENTROPY_PLUGIN
>
> ifeq ($(PLUGINCC),)
> ifneq ($(GCC_PLUGINS_CFLAGS),)

> [...]

> diff --git a/scripts/gcc-plugins/latent_entropy_plugin.c b/scripts/gcc-plugins/latent_entropy_plugin.c
> new file mode 100644
> index 0000000..f606caa
> --- /dev/null
> +++ b/scripts/gcc-plugins/latent_entropy_plugin.c
> @@ -0,0 +1,454 @@
> +/*
> + * Copyright 2012-2016 by the PaX Team <page...@freemail.hu>
> + * Copyright 2016 by Emese Revfy <re.e...@gmail.com>
> + * Licensed under the GPL v2
> + *
> + * Note: the choice of the license means that the compilation process is
> + * NOT 'eligible' as defined by gcc's library exception to the GPL v3,
> + * but for the kernel it doesn't matter since it doesn't link against
> + * any of the gcc libraries
> + *
> + * gcc plugin to help generate a little bit of entropy from program state,
> + * used throughout the uptime of the kernel

I think this comment needs a lot of expanding. What are all the ways
that this plugin makes changes to code? Things I think I see are:
pre-filling data variables with randomness, creating a local_entropy
variable (local to what?), mixing stack pointer (into what?), updating
latent_entropy global.

Please add some comments above this function about why the seed is
chosen this way, how it is expected to change over the lifetime of the
plugin, etc.

> +static tree handle_latent_entropy_attribute(tree *node, tree name, tree args __unused, int flags __unused, bool *no_add_attrs)

Can you add comments to each section below describing what's being
checked for? Or describe above the function what specific situations
are valid for using the attribute? (The latter patch says "functions",
but also marks other kinds of things.)

What is happening here? Is this populating integers with the random
const? (I assume the ARRAY_TYPE version of this is the same thing,
only multiple times. Could that be made into a function instead of
cut/paste with a loop in the ARRAY_TYPE case below?

> +
> + case ARRAY_TYPE: {
> + tree elt_type, array_size, elt_size;
> + unsigned int i, nelt;
> +
> + elt_type = TREE_TYPE(type);
> + elt_size = TYPE_SIZE_UNIT(TREE_TYPE(type));
> + array_size = TYPE_SIZE_UNIT(type);
> +
> + if (TREE_CODE(elt_type) != INTEGER_TYPE || !array_size || TREE_CODE(array_size) != INTEGER_CST) {
> + *no_add_attrs = true;
> + error("array variable %qD with %qE attribute must be a fixed length integer array type", *node, name);
> + break;
> + }
> +
> + nelt = TREE_INT_CST_LOW(array_size) / TREE_INT_CST_LOW(elt_size);
> +#if BUILDING_GCC_VERSION <= 4007
> + vals = VEC_alloc(constructor_elt, gc, nelt);
> +#else
> + vec_alloc(vals, nelt);
> +#endif
> +
> + mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(elt_type)) - 1);
> + mask = 2 * (mask - 1) + 1;

This mask calculation appears to be cut/pasted. Should it be a macro
or function taking "type" instead?

Please describe this state machine, and why it does what it does. :)

> +{
> + static enum tree_code op;
> + unsigned HOST_WIDE_INT random_const;
> +
> + random_const = get_random_const();
> +
> + switch (op) {
> + case BIT_XOR_EXPR:
> + op = PLUS_EXPR;
> + break;
> +
> + case PLUS_EXPR:
> + if (rhs) {
> + op = LROTATE_EXPR;
> + random_const &= HOST_BITS_PER_WIDE_INT - 1;
> + break;
> + }

What's happening here with the random_const?

> +
> + case LROTATE_EXPR:
> + default:
> + op = BIT_XOR_EXPR;
> + break;
> + }
> + if (rhs)
> + *rhs = build_int_cstu(unsigned_intDI_type_node, random_const);
> + return op;
> +}
> +
> +static void perturb_local_entropy(basic_block bb, tree local_entropy)

What effect does this function have on the resulting code output?

> +{
> + gimple_stmt_iterator gsi;
> + gimple assign;
> + tree rhs;
> + enum tree_code subcode;
> +
> + subcode = get_op(&rhs);
> + assign = gimple_build_assign_with_ops(subcode, local_entropy, local_entropy, rhs);
> + gsi = gsi_after_labels(bb);
> + gsi_insert_before(&gsi, assign, GSI_NEW_STMT);
> + update_stmt(assign);
> +}
> +
> +static void perturb_latent_entropy(basic_block bb, tree rhs)

Same for this. I assume this is effectively:

u64 temp_latent_entropy;

temp_latent_entropy = latent_entropy;
temp_latent_entropy = temp_latent_entropy OP rhs
latent_entropy = temp_latent_entropy;

Where does rhs come from? (Is this the "local_entropy" below?)

What is the stack pointer mixed into?

This below needs a bit more detail in comments. IIUC, it's creating a
local (to the .o file? the basic block?) variable, initializing it
with the stack, perturbing it with random operations, then updating
the latent_entropy with it?

> + /* create local entropy variable */
> + local_entropy = create_a_tmp_var(unsigned_intDI_type_node, "local_entropy");

What value does local_entropy have initially?

> +
> + /* 1. stack pointer */
> + mix_in_sp(bb, local_entropy);
> +
> + bb = bb->next_bb;
> + /* 2. instrument each BB with an operation on the local entropy variable */
> + while (bb != EXIT_BLOCK_PTR_FOR_FN(cfun)) {
> + perturb_local_entropy(bb, local_entropy);
> + bb = bb->next_bb;
> + };
> +
> + /* 3. mix local entropy into the global entropy variable */
> + gcc_assert(single_pred_p(EXIT_BLOCK_PTR_FOR_FN(cfun)));
> + perturb_latent_entropy(single_pred(EXIT_BLOCK_PTR_FOR_FN(cfun)), local_entropy);
> + return 0;
> +}

> [...]

Thanks!

[Kees Cook]

By the way, as you work on v3, can you also be sure to put your
patches through scripts/checkpatch.pl? There are a lot of >80
character lines, and other nits. I'd like to minimize the warnings.

[Emese Revfy]

On Thu, 9 Jun 2016 14:18:08 -0700
Kees Cook <kees...@chromium.org> wrote:

> By the way, as you work on v3, can you also be sure to put your
> patches through scripts/checkpatch.pl? There are a lot of >80
> character lines, and other nits. I'd like to minimize the warnings.

I only split those lines where the split doesn't make the code worse.
I checked it again and I made some changes:
https://github.com/ephox-gcc-plugins/latent_entropy/commit/e8e7c885b49db16903ea5bd4d6318ce1246f85f3

--
Emese

[Emese Revfy]

On Thu, 9 Jun 2016 14:51:45 -0700
Kees Cook <kees...@chromium.org> wrote:

> On Mon, May 30, 2016 at 4:31 PM, Emese Revfy <re.e...@gmail.com> wrote:
> > - GCC_PLUGINS_CFLAGS := $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y))
> > + GCC_PLUGINS_CFLAGS := $(strip $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y)) $(gcc-plugin-cflags-y))
>
> Is this change part of latent_entropy, or a general fix to the gcc
> plugin infrastructure?

This is a new feature in the gcc plugin infrastructure. The latent_entropy plugin has an argument and
we must add it (with a space) to the cflags.

> > + * gcc plugin to help generate a little bit of entropy from program state,
> > + * used throughout the uptime of the kernel
>
> I think this comment needs a lot of expanding. What are all the ways
> that this plugin makes changes to code? Things I think I see are:
> pre-filling data variables with randomness, creating a local_entropy
> variable (local to what?), mixing stack pointer (into what?), updating
> latent_entropy global.

I demonstrated the details here:
https://github.com/ephox-gcc-plugins/latent_entropy/commit/049acd9f478d47ee6526d8e93ab8cfcc3ff91b13

> > +static unsigned HOST_WIDE_INT seed;
> > +static unsigned HOST_WIDE_INT get_random_const(void)
> > +{
> > + unsigned int i;
> > + unsigned HOST_WIDE_INT ret = 0;
> > +
> > + for (i = 0; i < 8 * sizeof ret; i++) {
> > + ret = (ret << 1) | (seed & 1);
> > + seed >>= 1;
> > + if (ret & 1)
> > + seed ^= 0xD800000000000000ULL;
> > + }
> > +
> > + return ret;
> > +}
>
> Please add some comments above this function about why the seed is
> chosen this way, how it is expected to change over the lifetime of the
> plugin, etc.

You can see the comments here:
https://github.com/ephox-gcc-plugins/latent_entropy/commit/4999276e866271c69186a8e3112c265b6a0f3205

> > +static tree handle_latent_entropy_attribute(tree *node, tree name, tree args __unused, int flags __unused, bool *no_add_attrs)
>
> Can you add comments to each section below describing what's being
> checked for? Or describe above the function what specific situations
> are valid for using the attribute? (The latter patch says "functions",
> but also marks other kinds of things.)

I think the error messages already describe all the wrong situations.
What would you like to see in addition to the existing error messages?

You can find a description about the attribute here:
https://github.com/ephox-gcc-plugins/latent_entropy/commit/f0ec66810682579109469b862ac5169aa2a743ca

> > + mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(type)) - 1);
> > + mask = 2 * (mask - 1) + 1;
> > +
> > + if (TYPE_UNSIGNED(type))
> > + DECL_INITIAL(*node) = build_int_cstu(type, mask & get_random_const());
> > + else
> > + DECL_INITIAL(*node) = build_int_cst(type, mask & get_random_const());
> > + break;
>
> What is happening here? Is this populating integers with the random
> const? (I assume the ARRAY_TYPE version of this is the same thing,
> only multiple times. Could that be made into a function instead of
> cut/paste with a loop in the ARRAY_TYPE case below?

https://github.com/ephox-gcc-plugins/latent_entropy/commit/d65864b6ca2e61cc73cd28309ba0779fde75b4f2

> > +static enum tree_code get_op(tree *rhs)
>
> Please describe this state machine, and why it does what it does. :)

https://github.com/ephox-gcc-plugins/latent_entropy/commit/c4cc18cfb5d37121fe62907bed6b5aaafb84fff8

> > +{
> > + static enum tree_code op;
> > + unsigned HOST_WIDE_INT random_const;
> > +
> > + random_const = get_random_const();
> > +
> > + switch (op) {
> > + case BIT_XOR_EXPR:
> > + op = PLUS_EXPR;
> > + break;
> > +
> > + case PLUS_EXPR:
> > + if (rhs) {
> > + op = LROTATE_EXPR;
> > + random_const &= HOST_BITS_PER_WIDE_INT - 1;
> > + break;
> > + }
>
> What's happening here with the random_const?

I wrote a comment, you can find it here:
https://github.com/ephox-gcc-plugins/latent_entropy/commit/da452fdbc0247095fdf2b1f52eb4ddd368fad640

> > +
> > + case LROTATE_EXPR:
> > + default:
> > + op = BIT_XOR_EXPR;
> > + break;
> > + }
> > + if (rhs)
> > + *rhs = build_int_cstu(unsigned_intDI_type_node, random_const);
> > + return op;
> > +}
> > +
> > +static void perturb_local_entropy(basic_block bb, tree local_entropy)
>
> What effect does this function have on the resulting code output?

Would you like to see more on top of this comment:
https://github.com/ephox-gcc-plugins/latent_entropy/commit/049acd9f478d47ee6526d8e93ab8cfcc3ff91b13

> > +static void perturb_latent_entropy(basic_block bb, tree rhs)
>
> Same for this. I assume this is effectively:
>
> u64 temp_latent_entropy;
>
> temp_latent_entropy = latent_entropy;
> temp_latent_entropy = temp_latent_entropy OP rhs
> latent_entropy = temp_latent_entropy;
>
> Where does rhs come from? (Is this the "local_entropy" below?)

Sure, I'll rename the rhs parameter to local_entropy.

> > +static void mix_in_sp(basic_block bb, tree local_entropy)
>
> What is the stack pointer mixed into?

I already wrote some comments:
https://github.com/ephox-gcc-plugins/latent_entropy/commit/d2781819d774b4370c248cdb8d0dd2b47308b6f4

> This below needs a bit more detail in comments. IIUC, it's creating a
> local (to the .o file? the basic block?) variable, initializing it
> with the stack, perturbing it with random operations, then updating
> the latent_entropy with it?
> > + /* create local entropy variable */
> > + local_entropy = create_a_tmp_var(unsigned_intDI_type_node, "local_entropy");
>
> What value does local_entropy have initially?

You can see it here:
https://github.com/ephox-gcc-plugins/latent_entropy/commit/049acd9f478d47ee6526d8e93ab8cfcc3ff91b13

--
Emese

[Kees Cook]

On Mon, Jun 13, 2016 at 2:49 PM, Emese Revfy <re.e...@gmail.com> wrote:
> On Thu, 9 Jun 2016 14:51:45 -0700
> Kees Cook <kees...@chromium.org> wrote:
>
>> On Mon, May 30, 2016 at 4:31 PM, Emese Revfy <re.e...@gmail.com> wrote:
>> > - GCC_PLUGINS_CFLAGS := $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y))
>> > + GCC_PLUGINS_CFLAGS := $(strip $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y)) $(gcc-plugin-cflags-y))
>>
>> Is this change part of latent_entropy, or a general fix to the gcc
>> plugin infrastructure?
>
> This is a new feature in the gcc plugin infrastructure. The latent_entropy plugin has an argument and
> we must add it (with a space) to the cflags.

Okay, can you break this out into a separate commit?

>
>> > + * gcc plugin to help generate a little bit of entropy from program state,
>> > + * used throughout the uptime of the kernel
>>
>> I think this comment needs a lot of expanding. What are all the ways
>> that this plugin makes changes to code? Things I think I see are:
>> pre-filling data variables with randomness, creating a local_entropy
>> variable (local to what?), mixing stack pointer (into what?), updating
>> latent_entropy global.
>
> I demonstrated the details here:
> https://github.com/ephox-gcc-plugins/latent_entropy/commit/049acd9f478d47ee6526d8e93ab8cfcc3ff91b13

That helps, thanks. Can you also mention how __latent_entropy changes
non-functions? (i.e. initializes them with random data.)

Also, I think this isn't accurate:

* local_entropy ^= get_random_long();

Looking at the disassembly, it seems that static random values (i.e.
randomly chosen at gcc runtime) are added, rather than making calls to
the kernel's get_random_long() function.

>> > +static unsigned HOST_WIDE_INT seed;
>> > +static unsigned HOST_WIDE_INT get_random_const(void)
>> > +{
>> > + unsigned int i;
>> > + unsigned HOST_WIDE_INT ret = 0;
>> > +
>> > + for (i = 0; i < 8 * sizeof ret; i++) {
>> > + ret = (ret << 1) | (seed & 1);
>> > + seed >>= 1;
>> > + if (ret & 1)
>> > + seed ^= 0xD800000000000000ULL;
>> > + }
>> > +
>> > + return ret;
>> > +}
>>
>> Please add some comments above this function about why the seed is
>> chosen this way, how it is expected to change over the lifetime of the
>> plugin, etc.
>
> You can see the comments here:
> https://github.com/ephox-gcc-plugins/latent_entropy/commit/4999276e866271c69186a8e3112c265b6a0f3205

Ah-ha, thanks. I missed the assignment of "seed" during the init phase.

>> > +static tree handle_latent_entropy_attribute(tree *node, tree name, tree args __unused, int flags __unused, bool *no_add_attrs)
>>
>> Can you add comments to each section below describing what's being
>> checked for? Or describe above the function what specific situations
>> are valid for using the attribute? (The latter patch says "functions",
>> but also marks other kinds of things.)
>
> I think the error messages already describe all the wrong situations.
> What would you like to see in addition to the existing error messages?
>
> You can find a description about the attribute here:
> https://github.com/ephox-gcc-plugins/latent_entropy/commit/f0ec66810682579109469b862ac5169aa2a743ca

I think that clears it up nicely.

>
>> > + mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(type)) - 1);
>> > + mask = 2 * (mask - 1) + 1;
>> > +
>> > + if (TYPE_UNSIGNED(type))
>> > + DECL_INITIAL(*node) = build_int_cstu(type, mask & get_random_const());
>> > + else
>> > + DECL_INITIAL(*node) = build_int_cst(type, mask & get_random_const());
>> > + break;
>>
>> What is happening here? Is this populating integers with the random
>> const? (I assume the ARRAY_TYPE version of this is the same thing,
>> only multiple times. Could that be made into a function instead of
>> cut/paste with a loop in the ARRAY_TYPE case below?
>
> https://github.com/ephox-gcc-plugins/latent_entropy/commit/d65864b6ca2e61cc73cd28309ba0779fde75b4f2

Great! This is much more readable to me.

>> > +static enum tree_code get_op(tree *rhs)
>>
>> Please describe this state machine, and why it does what it does. :)
>
> https://github.com/ephox-gcc-plugins/latent_entropy/commit/c4cc18cfb5d37121fe62907bed6b5aaafb84fff8

Great!

>
>> > +{
>> > + static enum tree_code op;
>> > + unsigned HOST_WIDE_INT random_const;
>> > +
>> > + random_const = get_random_const();
>> > +
>> > + switch (op) {
>> > + case BIT_XOR_EXPR:
>> > + op = PLUS_EXPR;
>> > + break;
>> > +
>> > + case PLUS_EXPR:
>> > + if (rhs) {
>> > + op = LROTATE_EXPR;
>> > + random_const &= HOST_BITS_PER_WIDE_INT - 1;
>> > + break;
>> > + }
>>
>> What's happening here with the random_const?
>
> I wrote a comment, you can find it here:
> https://github.com/ephox-gcc-plugins/latent_entropy/commit/da452fdbc0247095fdf2b1f52eb4ddd368fad640
>

Thanks!

>> > +
>> > + case LROTATE_EXPR:
>> > + default:
>> > + op = BIT_XOR_EXPR;
>> > + break;
>> > + }
>> > + if (rhs)
>> > + *rhs = build_int_cstu(unsigned_intDI_type_node, random_const);
>> > + return op;
>> > +}
>> > +
>> > +static void perturb_local_entropy(basic_block bb, tree local_entropy)
>>
>> What effect does this function have on the resulting code output?
>
> Would you like to see more on top of this comment:
> https://github.com/ephox-gcc-plugins/latent_entropy/commit/049acd9f478d47ee6526d8e93ab8cfcc3ff91b13

I think that comment should be fine.

>> > +static void perturb_latent_entropy(basic_block bb, tree rhs)
>>
>> Same for this. I assume this is effectively:
>>
>> u64 temp_latent_entropy;
>>
>> temp_latent_entropy = latent_entropy;
>> temp_latent_entropy = temp_latent_entropy OP rhs
>> latent_entropy = temp_latent_entropy;
>>
>> Where does rhs come from? (Is this the "local_entropy" below?)
>
> Sure, I'll rename the rhs parameter to local_entropy.

Thanks.

>
>> > +static void mix_in_sp(basic_block bb, tree local_entropy)
>>
>> What is the stack pointer mixed into?
>
> I already wrote some comments:
> https://github.com/ephox-gcc-plugins/latent_entropy/commit/d2781819d774b4370c248cdb8d0dd2b47308b6f4

Awesome.

>> This below needs a bit more detail in comments. IIUC, it's creating a
>> local (to the .o file? the basic block?) variable, initializing it
>> with the stack, perturbing it with random operations, then updating
>> the latent_entropy with it?
>> > + /* create local entropy variable */
>> > + local_entropy = create_a_tmp_var(unsigned_intDI_type_node, "local_entropy");
>>
>> What value does local_entropy have initially?
>
> You can see it here:
> https://github.com/ephox-gcc-plugins/latent_entropy/commit/049acd9f478d47ee6526d8e93ab8cfcc3ff91b13

Got it, thanks. These changes look great. If you can send an updated
series for latent_entropy, I'll add it to -next.

[Emese Revfy]

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

scripts/Makefile.gcc-plugins | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/scripts/Makefile.gcc-plugins b/scripts/Makefile.gcc-plugins
index 5e22b60..da7f86c 100644
--- a/scripts/Makefile.gcc-plugins
+++ b/scripts/Makefile.gcc-plugins
@@ -19,7 +19,7 @@ ifdef CONFIG_GCC_PLUGINS
endif
endif

- GCC_PLUGINS_CFLAGS := $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y))
+ GCC_PLUGINS_CFLAGS := $(strip $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y)) $(gcc-plugin-cflags-y))

export PLUGINCC GCC_PLUGINS_CFLAGS GCC_PLUGIN SANCOV_PLUGIN

--
2.8.1

[Emese Revfy]

I would like to introduce the latent_entropy gcc plugin. This plugin mitigates
the problem of the kernel having too little entropy during and after boot
for generating crypto keys.

This plugin mixes random values into the latent_entropy global variable
in functions marked by the __latent_entropy attribute.
The value of this global variable is added to the kernel entropy pool
to increase the entropy.

It is a CII project supported by the Linux Foundation.

The latent_entropy plugin was ported from grsecurity/PaX originally written by
the PaX Team. You can find more about the plugin here:
https://grsecurity.net/pipermail/grsecurity/2012-July/001093.html

The plugin supports all gcc version from 4.5 to 6.0.

I do some changes above the PaX version. The important one is mixing
the stack pointer into the global variable too.
You can find more about the changes here:
https://github.com/ephox-gcc-plugins/latent_entropy

This patch set is based on the "Introduce GCC plugin infrastructure" patch set (v9 next-20160520).

Emese Revfy (4):
Add support for passing gcc plugin arguments

Add the latent_entropy gcc plugin
Mark functions with the latent_entropy attribute
Add the extra_latent_entropy kernel parameter

Changes from v2:
* Moved the passing of gcc plugin arguments into a separate patch

(Suggested-by: Kees Cook <kees...@chromium.org>)

* Mix the global entropy variable with the stack pointer (latent_entropy_plugin.c)
* Handle tail calls (latent_entropy_plugin.c)
* Fix some indentation related warnings suggested by checkpatch.pl (latent_entropy_plugin.c)
* Commented some latent_entropy plugin code

(Suggested-by: Kees Cook <kees...@chromium.org>)

Changes from v1:
* Remove unnecessary ifdefs
(Suggested-by: Kees Cook <kees...@chromium.org>)
* Separate the two definitions of add_latent_entropy()
(Suggested-by: Kees Cook <kees...@chromium.org>)
* Removed unnecessary global variable (latent_entropy_plugin.c)
* About the latent_entropy gcc attribute (latent_entropy_plugin.c)
* Measure the boot time performance impact of the latent_entropy plugin (arch/Kconfig)

---
Documentation/kernel-parameters.txt | 5 +
arch/Kconfig | 23 ++
arch/powerpc/kernel/Makefile | 8 +-
block/blk-softirq.c | 2 +-
drivers/char/random.c | 6 +-
fs/namespace.c | 2 +-

include/linux/compiler-gcc.h | 7 +

include/linux/compiler.h | 4 +
include/linux/fdtable.h | 2 +-
include/linux/genhd.h | 2 +-
include/linux/init.h | 4 +-
include/linux/random.h | 14 +-
init/main.c | 1 +
kernel/fork.c | 5 +-
kernel/rcu/tiny.c | 2 +-
kernel/rcu/tree.c | 2 +-
kernel/sched/fair.c | 2 +-
kernel/softirq.c | 4 +-
kernel/time/timer.c | 2 +-
lib/irq_poll.c | 2 +-
lib/random32.c | 2 +-
mm/page_alloc.c | 30 ++
net/core/dev.c | 4 +-

scripts/Makefile.gcc-plugins | 10 +-
scripts/gcc-plugins/Makefile | 1 +

scripts/gcc-plugins/latent_entropy_plugin.c | 597 ++++++++++++++++++++++++++++
26 files changed, 714 insertions(+), 29 deletions(-)

[Emese Revfy]

The latent_entropy gcc attribute can be only on functions and variables.

If it is on a function then the plugin will instrument it. If the attribute

is on a variable then the plugin will initialize it with a random value.

The variable must be an integer, an integer array type or a structure with integer fields.

These functions have been selected because they are init functions or
are called at random times or they have variable loops.

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

block/blk-softirq.c | 2 +-
drivers/char/random.c | 6 +++---
fs/namespace.c | 2 +-
include/linux/compiler-gcc.h | 7 +++++++
include/linux/compiler.h | 4 ++++

include/linux/fdtable.h | 2 +-
include/linux/genhd.h | 2 +-

include/linux/init.h | 4 ++--
include/linux/random.h | 4 ++--
kernel/fork.c | 4 ++--

kernel/rcu/tiny.c | 2 +-
kernel/rcu/tree.c | 2 +-
kernel/sched/fair.c | 2 +-

kernel/softirq.c | 4 ++--

kernel/time/timer.c | 2 +-
lib/irq_poll.c | 2 +-
lib/random32.c | 2 +-

mm/page_alloc.c | 2 +-
net/core/dev.c | 4 ++--

19 files changed, 35 insertions(+), 24 deletions(-)

index e294939..0ef8329 100644
--- a/include/linux/compiler-gcc.h
+++ b/include/linux/compiler-gcc.h
@@ -188,6 +188,13 @@

#endif /* GCC_VERSION >= 40300 */

#if GCC_VERSION >= 40500
+

+#ifndef __CHECKER__

diff --git a/include/linux/random.h b/include/linux/random.h
index 752e7df..d286d51 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h

@@ -29,8 +29,8 @@ static inline void add_latent_entropy(void) {}
#endif

extern void add_input_randomness(unsigned int type, unsigned int code,

- unsigned int value);
-extern void add_interrupt_randomness(int irq, int irq_flags);
+ unsigned int value) __latent_entropy;
+extern void add_interrupt_randomness(int irq, int irq_flags) __latent_entropy;

extern void get_random_bytes(void *buf, int nbytes);
extern int add_random_ready_callback(struct random_ready_callback *rdy);

diff --git a/kernel/fork.c b/kernel/fork.c
index d07d5a6..9fba65c 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index d10324e..ffc4f4a 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c

[Emese Revfy]

This plugin mitigates the problem of the kernel having too little entropy during
and after boot for generating crypto keys.

It creates a local variable in every marked function. The value of this variable is
modified by randomly chosen operations (add, xor and rol) and
random values (gcc generates them at compile time and the stack pointer at runtime).
It depends on the control flow (e.g., loops, conditions).

Before the function returns the plugin writes this local variable

into the latent_entropy global variable. The value of this global variable is
added to the kernel entropy pool in do_one_initcall() and _do_fork().

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

arch/Kconfig | 18 +

arch/powerpc/kernel/Makefile | 8 +-
include/linux/random.h | 10 +
init/main.c | 1 +
kernel/fork.c | 1 +
mm/page_alloc.c | 5 +

scripts/Makefile.gcc-plugins | 8 +-

scripts/gcc-plugins/Makefile | 1 +
scripts/gcc-plugins/latent_entropy_plugin.c | 597 ++++++++++++++++++++++++++++

9 files changed, 644 insertions(+), 5 deletions(-)

create mode 100644 scripts/gcc-plugins/latent_entropy_plugin.c

diff --git a/arch/Kconfig b/arch/Kconfig

index 566f922..c099ebd 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -394,6 +394,24 @@ config GCC_PLUGIN_SANCOV

diff --git a/include/linux/random.h b/include/linux/random.h
index e47e533..752e7df 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h

@@ -18,6 +18,16 @@ struct random_ready_callback {
};

extern void add_device_randomness(const void *, unsigned int);
+

+#if defined(CONFIG_GCC_PLUGIN_LATENT_ENTROPY) && !defined(__CHECKER__)

+static inline void add_latent_entropy(void)
+{
+ add_device_randomness((const void *)&latent_entropy, sizeof(latent_entropy));
+}
+#else
+static inline void add_latent_entropy(void) {}
+#endif
+

extern void add_input_randomness(unsigned int type, unsigned int code,

unsigned int value);

extern void add_interrupt_randomness(int irq, int irq_flags);

diff --git a/init/main.c b/init/main.c
index 4c17fda..07e4174 100644
--- a/init/main.c
+++ b/init/main.c
@@ -781,6 +781,7 @@ int __init_or_module do_one_initcall(initcall_t fn)
}
WARN(msgbuf[0], "initcall %pF returned with %s\n", fn, msgbuf);

+ add_latent_entropy();
return ret;
}

diff --git a/kernel/fork.c b/kernel/fork.c
index cdf520f..d07d5a6 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c

@@ -1766,6 +1766,7 @@ long _do_fork(unsigned long clone_flags,

p = copy_process(clone_flags, stack_start, stack_size,
child_tidptr, NULL, trace, tls, NUMA_NO_NODE);
+ add_latent_entropy();
/*
* Do this prior waking up the new thread - the thread pointer
* might get invalid after that point, if the thread exits quickly.

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index f8f3bfc..d10324e 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c

@@ -1234,6 +1234,11 @@ static void __free_pages_ok(struct page *page, unsigned int order)
local_irq_restore(flags);
}

+#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
+volatile u64 latent_entropy;
+EXPORT_SYMBOL(latent_entropy);
+#endif
+
static void __init __free_pages_boot_core(struct page *page, unsigned int order)
{
unsigned int nr_pages = 1 << order;

diff --git a/scripts/Makefile.gcc-plugins b/scripts/Makefile.gcc-plugins
index da7f86c..cd7902c 100644
--- a/scripts/Makefile.gcc-plugins
+++ b/scripts/Makefile.gcc-plugins

@@ -6,6 +6,12 @@ ifdef CONFIG_GCC_PLUGINS

gcc-plugin-$(CONFIG_GCC_PLUGIN_CYC_COMPLEXITY) += cyc_complexity_plugin.so

+ gcc-plugin-$(CONFIG_GCC_PLUGIN_LATENT_ENTROPY) += latent_entropy_plugin.so
+ gcc-plugin-cflags-$(CONFIG_GCC_PLUGIN_LATENT_ENTROPY) += -DLATENT_ENTROPY_PLUGIN
+ ifdef CONFIG_PAX_LATENT_ENTROPY
+ DISABLE_LATENT_ENTROPY_PLUGIN += -fplugin-arg-latent_entropy_plugin-disable
+ endif
+
ifdef CONFIG_GCC_PLUGIN_SANCOV
ifeq ($(CFLAGS_KCOV),)
# It is needed because of the gcc-plugin.sh and gcc version checks.

@@ -21,7 +27,7 @@ ifdef CONFIG_GCC_PLUGINS

GCC_PLUGINS_CFLAGS := $(strip $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y)) $(gcc-plugin-cflags-y))

- export PLUGINCC GCC_PLUGINS_CFLAGS GCC_PLUGIN SANCOV_PLUGIN
+ export PLUGINCC GCC_PLUGINS_CFLAGS GCC_PLUGIN SANCOV_PLUGIN DISABLE_LATENT_ENTROPY_PLUGIN

ifeq ($(PLUGINCC),)
ifneq ($(GCC_PLUGINS_CFLAGS),)

diff --git a/scripts/gcc-plugins/Makefile b/scripts/gcc-plugins/Makefile
index 88c8ec4..a3f8ca4a 100644
--- a/scripts/gcc-plugins/Makefile
+++ b/scripts/gcc-plugins/Makefile
@@ -23,5 +23,6 @@ always := $($(HOSTLIBS)-y)

cyc_complexity_plugin-objs := cyc_complexity_plugin.o
sancov_plugin-objs := sancov_plugin.o
+latent_entropy_plugin-objs := latent_entropy_plugin.o

clean-files += *.so

diff --git a/scripts/gcc-plugins/latent_entropy_plugin.c b/scripts/gcc-plugins/latent_entropy_plugin.c
new file mode 100644

index 0000000..8a70e38
--- /dev/null
+++ b/scripts/gcc-plugins/latent_entropy_plugin.c
@@ -0,0 +1,597 @@

+/*
+ * Copyright 2012-2016 by the PaX Team <page...@freemail.hu>
+ * Copyright 2016 by Emese Revfy <re.e...@gmail.com>
+ * Licensed under the GPL v2
+ *
+ * Note: the choice of the license means that the compilation process is
+ * NOT 'eligible' as defined by gcc's library exception to the GPL v3,
+ * but for the kernel it doesn't matter since it doesn't link against
+ * any of the gcc libraries
+ *

+ * This gcc plugin helps generate a little bit of entropy from program state,
+ * used throughout the uptime of the kernel. Here is an instrumentation example:
+ *
+ * before:
+ * void __latent_entropy test(int argc, char *argv[])
+ * {
+ * printf("%u %s\n", argc, *argv);
+ * }
+ *
+ * after:
+ * void __latent_entropy test(int argc, char *argv[])
+ * {
+ * // latent_entropy_execute() 1.
+ * unsigned long local_entropy;
+ * // init_local_entropy() 1.
+ * void *local_entropy_frame_addr;
+ * // init_local_entropy() 3.
+ * unsigned long temp_latent_entropy;
+ *
+ * // init_local_entropy() 2.
+ * local_entropy_frame_addr = __builtin_frame_address(0);
+ * local_entropy = (unsigned long) local_entropy_frame_addr;
+ *
+ * // init_local_entropy() 4.
+ * temp_latent_entropy = latent_entropy;
+ * // init_local_entropy() 5.
+ * local_entropy ^= temp_latent_entropy;
+ *
+ * // latent_entropy_execute() 3.
+ * local_entropy += 4623067384293424948;
+ *
+ * printf("%u %s\n", argc, *argv);
+ *
+ * // latent_entropy_execute() 4.
+ * temp_latent_entropy = rol(temp_latent_entropy, local_entropy);
+ * latent_entropy = temp_latent_entropy;
+ * }
+ *
+ * It would look like this in C:
+ *
+ * unsigned long local_entropy = latent_entropy;
+ * local_entropy ^= 1234567890;
+ * local_entropy ^= (unsigned long)__builtin_frame_address(0);
+ * local_entropy += 9876543210;
+ * latent_entropy = rol(local_entropy, 1234509876);

+ *
+ * TODO:
+ * - add ipa pass to identify not explicitly marked candidate functions
+ * - mix in more program state (function arguments/return values,

+ * loop variables, etc)

+ * - more instrumentation control via attribute parameters
+ *
+ * BUGS:
+ * - none known
+ *
+ * Options:
+ * -fplugin-arg-latent_entropy_plugin-disable
+ *
+ * Attribute: __attribute__((latent_entropy))

+ * The latent_entropy gcc attribute can be only on functions and variables.
+ * If it is on a function then the plugin will instrument it. If the attribute
+ * is on a variable then the plugin will initialize it with a random value.
+ * The variable must be an integer, an integer array type or a structure
+ * with integer fields.

+ */
+
+#include "gcc-common.h"
+
+int plugin_is_GPL_compatible;
+
+static GTY(()) tree latent_entropy_decl;
+
+static struct plugin_info latent_entropy_plugin_info = {

+ .version = "201606141920",

+ .help = "disable\tturn off latent entropy instrumentation\n",
+};
+
+static unsigned HOST_WIDE_INT seed;

+/*
+ * get_random_seed() (this is a GCC function) generates the seed.
+ * This is a simple random generator without any cryptographic security because
+ * the entropy doesn't come from here.
+ */

+static unsigned HOST_WIDE_INT get_random_const(void)
+{
+ unsigned int i;
+ unsigned HOST_WIDE_INT ret = 0;
+
+ for (i = 0; i < 8 * sizeof ret; i++) {
+ ret = (ret << 1) | (seed & 1);
+ seed >>= 1;
+ if (ret & 1)
+ seed ^= 0xD800000000000000ULL;
+ }
+
+ return ret;
+}

+
+static tree tree_get_random_const(tree type)
+{

+ unsigned long long mask;
+

+ mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(type)) - 1);
+ mask = 2 * (mask - 1) + 1;
+
+ if (TYPE_UNSIGNED(type))

+ return build_int_cstu(type, mask & get_random_const());
+ return build_int_cst(type, mask & get_random_const());
+}
+

+static tree handle_latent_entropy_attribute(tree *node, tree name, tree args __unused, int flags __unused, bool *no_add_attrs)

+{
+ tree type;

+#if BUILDING_GCC_VERSION <= 4007
+ VEC(constructor_elt, gc) *vals;
+#else
+ vec<constructor_elt, va_gc> *vals;
+#endif
+
+ switch (TREE_CODE(*node)) {
+ default:
+ *no_add_attrs = true;
+ error("%qE attribute only applies to functions and variables", name);

+ break;
+

+ case VAR_DECL:
+ if (DECL_INITIAL(*node)) {
+ *no_add_attrs = true;
+ error("variable %qD with %qE attribute must not be initialized", *node, name);
+ break;
+ }
+
+ if (!TREE_STATIC(*node)) {
+ *no_add_attrs = true;
+ error("variable %qD with %qE attribute must not be local", *node, name);
+ break;
+ }
+
+ type = TREE_TYPE(*node);
+ switch (TREE_CODE(type)) {
+ default:
+ *no_add_attrs = true;
+ error("variable %qD with %qE attribute must be an integer"

+ " or a fixed length integer array type"

+ " or a fixed sized structure with integer fields", *node, name);

+ break;
+

+ case RECORD_TYPE: {
+ tree field;

+ unsigned int nelt = 0;
+

+ for (field = TYPE_FIELDS(type); field; nelt++, field = TREE_CHAIN(field)) {
+ tree fieldtype;
+
+ fieldtype = TREE_TYPE(field);
+ if (TREE_CODE(fieldtype) == INTEGER_TYPE)
+ continue;
+
+ *no_add_attrs = true;
+ error("structure variable %qD with %qE attribute has"

+ " a non-integer field %qE", *node, name, field);

+ break;
+ }
+
+ if (field)
+ break;
+
+#if BUILDING_GCC_VERSION <= 4007
+ vals = VEC_alloc(constructor_elt, gc, nelt);
+#else
+ vec_alloc(vals, nelt);
+#endif
+
+ for (field = TYPE_FIELDS(type); field; field = TREE_CHAIN(field)) {

+ tree random_const;
+
+ random_const = tree_get_random_const(TREE_TYPE(field));
+ CONSTRUCTOR_APPEND_ELT(vals, field, random_const);
+ }
+
+ /* Initialize the fields with random constants */

+ DECL_INITIAL(*node) = build_constructor(type, vals);
+ break;
+ }
+

+ /* Initialize the variable with a random constant */
+ case INTEGER_TYPE:
+ DECL_INITIAL(*node) = tree_get_random_const(type);
+ break;
+

+ case ARRAY_TYPE: {
+ tree elt_type, array_size, elt_size;
+ unsigned int i, nelt;
+
+ elt_type = TREE_TYPE(type);
+ elt_size = TYPE_SIZE_UNIT(TREE_TYPE(type));
+ array_size = TYPE_SIZE_UNIT(type);
+
+ if (TREE_CODE(elt_type) != INTEGER_TYPE || !array_size || TREE_CODE(array_size) != INTEGER_CST) {
+ *no_add_attrs = true;
+ error("array variable %qD with %qE attribute must be"

+ " a fixed length integer array type", *node, name);

+ break;
+ }
+
+ nelt = TREE_INT_CST_LOW(array_size) / TREE_INT_CST_LOW(elt_size);
+#if BUILDING_GCC_VERSION <= 4007
+ vals = VEC_alloc(constructor_elt, gc, nelt);
+#else
+ vec_alloc(vals, nelt);
+#endif

+
+ for (i = 0; i < nelt; i++) {
+ tree random_const = tree_get_random_const(elt_type);
+
+ CONSTRUCTOR_APPEND_ELT(vals, size_int(i), random_const);
+ }
+
+ /* Initialize the elements of the array with random constants */

+ DECL_INITIAL(*node) = build_constructor(type, vals);
+ break;
+ }
+ }

+ break;
+

+/*
+ * Set up the next operation and its constant operand to use in the latent
+ * entropy PRNG. When RHS is specified, the request is for perturbing the
+ * local latent entropy variable, otherwise it is for perturbing the global
+ * latent entropy variable where the two operands are already given by the
+ * local and global latent entropy variables themselves.
+ *
+ * The operation is one of add/xor/rol when instrumenting the local entropy
+ * variable and one of add/xor when perturbing the global entropy variable.
+ * Rotation is not used for the latter case because it would transmit less
+ * entropy to the global variable than the other two operations.
+ */

+static enum tree_code get_op(tree *rhs)

+{
+ static enum tree_code op;
+ unsigned HOST_WIDE_INT random_const;
+
+ random_const = get_random_const();
+
+ switch (op) {
+ case BIT_XOR_EXPR:
+ op = PLUS_EXPR;
+ break;
+
+ case PLUS_EXPR:
+ if (rhs) {
+ op = LROTATE_EXPR;

+ /*
+ * This code limits the value of random_const to
+ * the size of a wide int for the rotation
+ */

+ random_const &= HOST_BITS_PER_WIDE_INT - 1;
+ break;
+ }

+
+ case LROTATE_EXPR:
+ default:
+ op = BIT_XOR_EXPR;
+ break;
+ }
+ if (rhs)
+ *rhs = build_int_cstu(unsigned_intDI_type_node, random_const);
+ return op;
+}
+
+static void perturb_local_entropy(basic_block bb, tree local_entropy)

+{
+ gimple_stmt_iterator gsi;
+ gimple assign;
+ tree rhs;

+ enum tree_code op;
+
+ op = get_op(&rhs);
+ assign = gimple_build_assign_with_ops(op, local_entropy, local_entropy, rhs);

+ gsi = gsi_after_labels(bb);
+ gsi_insert_before(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+}
+

+static void __perturb_latent_entropy(gimple_stmt_iterator *gsi, tree local_entropy)
+{

+ gimple assign;
+ tree temp;

+ enum tree_code op;
+
+ /* 1. create temporary copy of latent_entropy */

+ temp = create_a_tmp_var(unsigned_intDI_type_node, "temp_latent_entropy");
+

+ /* 2. read... */

+ add_referenced_var(latent_entropy_decl);
+ mark_sym_for_renaming(latent_entropy_decl);
+ assign = gimple_build_assign(temp, latent_entropy_decl);

+ gsi_insert_before(gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+
+ /* 3. ...modify... */
+ op = get_op(NULL);
+ assign = gimple_build_assign_with_ops(op, temp, temp, local_entropy);
+ gsi_insert_after(gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+
+ /* 4. ...write latent_entropy */

+ assign = gimple_build_assign(latent_entropy_decl, temp);

+ gsi_insert_after(gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+}
+
+static bool handle_tail_calls(basic_block bb, tree local_entropy)

+{
+ gimple_stmt_iterator gsi;
+

+ for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
+ gcall *call;
+ gimple stmt = gsi_stmt(gsi);
+
+ if (!is_gimple_call(stmt))
+ continue;
+
+ call = as_a_gcall(stmt);
+ if (!gimple_call_tail_p(call))
+ continue;
+
+ __perturb_latent_entropy(&gsi, local_entropy);
+ return true;
+ }
+

+ return false;
+}
+

+static void perturb_latent_entropy(tree local_entropy)
+{
+ edge_iterator ei;
+ edge e, last_bb_e;
+ basic_block last_bb;
+
+ gcc_assert(single_pred_p(EXIT_BLOCK_PTR_FOR_FN(cfun)));
+ last_bb_e = single_pred_edge(EXIT_BLOCK_PTR_FOR_FN(cfun));
+
+ FOR_EACH_EDGE(e, ei, last_bb_e->src->preds) {
+ if (ENTRY_BLOCK_PTR_FOR_FN(cfun) == e->src)
+ continue;
+ if (EXIT_BLOCK_PTR_FOR_FN(cfun) == e->src)
+ continue;
+
+ handle_tail_calls(e->src, local_entropy);
+ }
+
+ last_bb = single_pred(EXIT_BLOCK_PTR_FOR_FN(cfun));
+ if (!handle_tail_calls(last_bb, local_entropy)) {
+ gimple_stmt_iterator gsi = gsi_last_bb(last_bb);
+
+ __perturb_latent_entropy(&gsi, local_entropy);
+ }
+}
+
+static void init_local_entropy(basic_block bb, tree local_entropy)

+{
+ gimple assign, call;

+ tree frame_addr, rand_const, temp, fndecl, udi_frame_addr;
+ enum tree_code op;

+ gimple_stmt_iterator gsi = gsi_after_labels(bb);
+

+ /* 1. create local_entropy_frame_addr */

+ frame_addr = create_a_tmp_var(ptr_type_node, "local_entropy_frame_addr");
+

+ /* 2. local_entropy_frame_addr = __builtin_frame_address() */
+ fndecl = builtin_decl_implicit(BUILT_IN_FRAME_ADDRESS);
+ call = gimple_build_call(fndecl, 1, integer_zero_node);

+ gimple_call_set_lhs(call, frame_addr);
+ gsi_insert_before(&gsi, call, GSI_NEW_STMT);
+ update_stmt(call);
+

+ udi_frame_addr = fold_convert(unsigned_intDI_type_node, frame_addr);
+ assign = gimple_build_assign(local_entropy, udi_frame_addr);

+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+

+ /* 3. create temporary copy of latent_entropy */

+ temp = create_a_tmp_var(unsigned_intDI_type_node, "temp_latent_entropy");
+

+ /* 4. read the global entropy variable into local entropy */

+ add_referenced_var(latent_entropy_decl);
+ mark_sym_for_renaming(latent_entropy_decl);
+ assign = gimple_build_assign(temp, latent_entropy_decl);

+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+

+ /* 5. mix local_entropy_frame_addr into local entropy */
+ assign = gimple_build_assign_with_ops(BIT_XOR_EXPR, local_entropy, local_entropy, temp);

+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+

+ rand_const = build_int_cstu(unsigned_intDI_type_node, get_random_const());

+ op = get_op(NULL);
+ assign = gimple_build_assign_with_ops(op, local_entropy, local_entropy, rand_const);

+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+}
+

+static bool create_latent_entropy_decl(void)
+{
+ varpool_node_ptr node;
+
+ if (latent_entropy_decl != NULL_TREE)
+ return true;

+
+ FOR_EACH_VARIABLE(node) {
+ tree var = NODE_DECL(node);
+
+ if (DECL_NAME_LENGTH(var) < sizeof("latent_entropy") - 1)
+ continue;
+ if (strcmp(IDENTIFIER_POINTER(DECL_NAME(var)), "latent_entropy"))
+ continue;
+
+ latent_entropy_decl = var;
+ break;
+ }
+

+ return latent_entropy_decl != NULL_TREE;
+}
+

+static unsigned int latent_entropy_execute(void)
+{
+ basic_block bb;
+ tree local_entropy;
+

+ if (!create_latent_entropy_decl())
+ return 0;
+
+ /* 2. initialize local entropy variable */

+ gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
+ bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
+ if (!single_pred_p(bb)) {
+ split_edge(single_succ_edge(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
+ gcc_assert(single_succ_p(ENTRY_BLOCK_PTR_FOR_FN(cfun)));
+ bb = single_succ(ENTRY_BLOCK_PTR_FOR_FN(cfun));
+ }
+

+ /* 1. create the local entropy variable */

+ local_entropy = create_a_tmp_var(unsigned_intDI_type_node, "local_entropy");

+
+ /* 2. initialize the local entropy variable */
+ init_local_entropy(bb, local_entropy);

+
+ bb = bb->next_bb;
+

+ /* 3. instrument each BB with an operation on the local entropy variable */

+ while (bb != EXIT_BLOCK_PTR_FOR_FN(cfun)) {
+ perturb_local_entropy(bb, local_entropy);
+ bb = bb->next_bb;
+ };
+

+ /* 4. mix local entropy into the global entropy variable */
+ perturb_latent_entropy(local_entropy);

+ return 0;
+}
+

+

[Emese Revfy]

On Tue, 14 Jun 2016 11:27:00 -0700

Kees Cook <kees...@chromium.org> wrote:

> On Mon, Jun 13, 2016 at 2:49 PM, Emese Revfy <re.e...@gmail.com> wrote:
> > On Thu, 9 Jun 2016 14:51:45 -0700
> > Kees Cook <kees...@chromium.org> wrote:
>
> >> > + * gcc plugin to help generate a little bit of entropy from program state,
> >> > + * used throughout the uptime of the kernel
> >>
> >> I think this comment needs a lot of expanding. What are all the ways
> >> that this plugin makes changes to code? Things I think I see are:
> >> pre-filling data variables with randomness, creating a local_entropy
> >> variable (local to what?), mixing stack pointer (into what?), updating
> >> latent_entropy global.
> >
> > I demonstrated the details here:
> > https://github.com/ephox-gcc-plugins/latent_entropy/commit/049acd9f478d47ee6526d8e93ab8cfcc3ff91b13
>
> That helps, thanks. Can you also mention how __latent_entropy changes
> non-functions? (i.e. initializes them with random data.)
>
> Also, I think this isn't accurate:
>
> * local_entropy ^= get_random_long();
>
> Looking at the disassembly, it seems that static random values (i.e.
> randomly chosen at gcc runtime) are added, rather than making calls to
> the kernel's get_random_long() function.

The plugin doesn't insert calls to the kernel's get_random_long().
That was just an example (the plugin instrumentation would look like this in the kernel).
I rewrote these calls to a random constant.

--
Emese

[Kees Cook]

On Tue, Jun 14, 2016 at 3:20 PM, Emese Revfy <re.e...@gmail.com> wrote:
> This plugin mitigates the problem of the kernel having too little entropy during
> and after boot for generating crypto keys.
>
> It creates a local variable in every marked function. The value of this variable is
> modified by randomly chosen operations (add, xor and rol) and
> random values (gcc generates them at compile time and the stack pointer at runtime).
> It depends on the control flow (e.g., loops, conditions).
>
> Before the function returns the plugin writes this local variable
> into the latent_entropy global variable. The value of this global variable is
> added to the kernel entropy pool in do_one_initcall() and _do_fork().
>
> Signed-off-by: Emese Revfy <re.e...@gmail.com>

> [...]

> diff --git a/arch/powerpc/kernel/Makefile b/arch/powerpc/kernel/Makefile
> index 2da380f..6c7e448 100644
> --- a/arch/powerpc/kernel/Makefile
> +++ b/arch/powerpc/kernel/Makefile
> @@ -16,10 +16,10 @@ endif
>
> ifdef CONFIG_FUNCTION_TRACER
> # Do not trace early boot code
> -CFLAGS_REMOVE_cputable.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
> -CFLAGS_REMOVE_prom_init.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
> -CFLAGS_REMOVE_btext.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
> -CFLAGS_REMOVE_prom.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
> +CFLAGS_REMOVE_cputable.o = -mno-sched-epilog $(CC_FLAGS_FTRACE) $(DISABLE_LATENT_ENTROPY_PLUGIN)
> +CFLAGS_REMOVE_prom_init.o = -mno-sched-epilog $(CC_FLAGS_FTRACE) $(DISABLE_LATENT_ENTROPY_PLUGIN)
> +CFLAGS_REMOVE_btext.o = -mno-sched-epilog $(CC_FLAGS_FTRACE) $(DISABLE_LATENT_ENTROPY_PLUGIN)
> +CFLAGS_REMOVE_prom.o = -mno-sched-epilog $(CC_FLAGS_FTRACE) $(DISABLE_LATENT_ENTROPY_PLUGIN)

This doesn't look right to me: these are CFLAGS_REMOVE_* entries, and
I think you want to _add_ the DISABLE_LATENT_ENTROPY_PLUGIN to the
CFLAGS here.

from scripts/Makefile.lib:
_c_flags = $(filter-out $(CFLAGS_REMOVE_$(basetarget).o), $(orig_c_flags))

[Kees Cook]

This continues to look great to me, thanks for all the added comments
and improvements.

One thing I'd still really like to see is that each patch passes
script/checkpatch.pl with as few issues as possible. The >80 character
lines are a problem, and I think they impede readability. Quoting from
Documentation/CodingStyle:


The limit on the length of lines is 80 columns and this is a strongly
preferred limit.

Statements longer than 80 columns will be broken into sensible chunks, unless
exceeding 80 columns significantly increases readability and does not hide
information. Descendants are always substantially shorter than the parent and
are placed substantially to the right. The same applies to function headers
with a long argument list. However, never break user-visible strings such as
printk messages, because that breaks the ability to grep for them.


Personally, I'm okay with exceptions where they make sense, but they
should be exceptions, as opposed to being common. Right now in this
series, there are a lot of cases of long lines even in places where it
isn't code, like in commit messages and Kconfig text.

Here's the current output from checkpatch.pl:

0002-Add-the-latent_entropy-gcc-plugin.patch
total: 5 errors, 54 warnings, 702 lines checked

0003-Mark-functions-with-the-latent_entropy-attribute.patch
total: 2 errors, 8 warnings, 0 checks, 197 lines checked

0004-Add-the-extra_latent_entropy-kernel-parameter.patch
total: 0 errors, 3 warnings, 65 lines checked

The 54 warnings in the plugin should get vastly reduced. You can
ignore things that aren't correct, like:

ERROR: Macros with complex values should be enclosed in parentheses
#148: FILE: include/linux/init.h:42:

+#define __init __section(.init.text) __cold notrace __latent_entropy

Obviously __init isn't a "regular" macro, etc. And other misparsings
can be ignored, like:

ERROR: spaces required around that '>' (ctx:VxW)
#310: FILE: scripts/gcc-plugins/latent_entropy_plugin.c:127:

+ vec<constructor_elt, va_gc> *vals;

^
since checkpatch doesn't know about such things.

But things like this should be fixed:

WARNING: line over 80 characters
#157: FILE: include/linux/init.h:95:

+#define __meminit __section(.meminit.text) __cold notrace
__latent_entropy

I'd expect it to look like:

#define __meminit __section(.meminit.text) __cold notrace \
__latent_entropy

And for function declarations:

WARNING: line over 80 characters
#185: FILE: kernel/fork.c:409:

+static __latent_entropy int dup_mmap(struct mm_struct *mm, struct
mm_struct *oldmm)

static __latent_entropy int dup_mmap(struct mm_struct *mm,
struct mm_struct *oldmm)

and for long code lines:

WARNING: line over 80 characters
#774: FILE: scripts/gcc-plugins/latent_entropy_plugin.c:591:

+ register_callback(plugin_name,
PLUGIN_REGISTER_GGC_ROOTS, NULL, (void *)&gt_ggc_r_gt_latent_entropy);

register_callback(plugin_name, PLUGIN_REGISTER_GGC_ROOTS,
NULL, (void *)&gt_ggc_r_gt_latent_entropy);

Cases of long text lines are an exception, though:

WARNING: line over 80 characters
#322: FILE: scripts/gcc-plugins/latent_entropy_plugin.c:139:

+ error("variable %qD with %qE attribute must
not be initialized", *node, name);

This should leave the text unbroken, but wrap the next part:

error("variable %qD with %qE attribute must
not be initialized",
*node, name);

Thanks!

[Emese Revfy]

On Wed, 15 Jun 2016 11:55:44 -0700
Kees Cook <kees...@chromium.org> wrote:

> The limit on the length of lines is 80 columns and this is a strongly
> preferred limit.

I think the code looks worse when it is truncated to 80 columns but
I'll do it and resend the patches.

--
Emese

[Emese Revfy]

Thanks for the report. I think this patch fixes it:
https://github.com/ephox-gcc-plugins/gcc-plugins_linux-next/commit/e7601ca00a0aeb5f6b96dc79a51a5089c4d32791

--
Emese

[Kees Cook]

Yup, that looks correct, thanks!

[Kees Cook]

Yup, I understand your concerns, but since we're optimizing for
readability by a larger audience that has agreed to the guidelines in
CodingStyle, this is what we get. :)

One area I'm unclear on with kernel coding style, though, is if
splitting all the stuff prior to function name onto a separate line is
"acceptable", since that solves most of the long lines where
__latent_entropy has been added. For example, I don't know which is
better:

All on one line (gmail may split this, but my intention is all one line):

static __latent_entropy void rcu_process_callbacks(struct
softirq_action *unused)

Types and attributes on a separate line:

static __latent_entropy void
rcu_process_callbacks(struct softirq_action *unused)

All arguments on the next line:

static __latent_entropy void rcu_process_callbacks(
struct
softirq_action *unused)


Greg, do you have a better sense of how to split (or not split) these
kinds of long lines?

[Joe Perches]

Another option is to add __latent_entropy the same way most
__printf uses are done - on a separate line before the function

__latent_entropy
static void foo(...)

[Emese Revfy]

I would like to introduce the latent_entropy gcc plugin. This plugin
mitigates the problem of the kernel having too little entropy during and
after boot for generating crypto keys.

This plugin mixes random values into the latent_entropy global variable
in functions marked by the __latent_entropy attribute.
The value of this global variable is added to the kernel entropy pool
to increase the entropy.

It is a CII project supported by the Linux Foundation.

The latent_entropy plugin was ported from grsecurity/PaX originally written
by the PaX Team. You can find more about the plugin here:
https://grsecurity.net/pipermail/grsecurity/2012-July/001093.html

The plugin supports all gcc version from 4.5 to 6.0.

I do some changes above the PaX version. The important one is mixing
the stack pointer into the global variable too.
You can find more about the changes here:
https://github.com/ephox-gcc-plugins/latent_entropy

This patch set is based on the "Introduce GCC plugin infrastructure"

patch set (git/mmarek/kbuild.git#kbuild HEAD: 543c37cb165049c3be).

Emese Revfy (4):
Add support for passing gcc plugin arguments
Add the latent_entropy gcc plugin
Mark functions with the latent_entropy attribute
Add the extra_latent_entropy kernel parameter

Changes from v3:
* Fix disabling latent_entropy on some powerpc files
(Reported-by: Kees Cook <kees...@chromium.org>)
* Truncate the lines into <= 80 columns to follow the kernel coding style

(Suggested-by: Kees Cook <kees...@chromium.org>)

Changes from v2:
* Moved the passing of gcc plugin arguments into a separate patch
(Suggested-by: Kees Cook <kees...@chromium.org>)
* Mix the global entropy variable with the stack pointer
(latent_entropy_plugin.c)
* Handle tail calls (latent_entropy_plugin.c)
* Fix some indentation related warnings suggested by checkpatch.pl
(latent_entropy_plugin.c)
* Commented some latent_entropy plugin code
(Suggested-by: Kees Cook <kees...@chromium.org>)

Changes from v1:
* Remove unnecessary ifdefs

(Suggested-by: Kees Cook <kees...@chromium.org>)

* Separate the two definitions of add_latent_entropy()

(Suggested-by: Kees Cook <kees...@chromium.org>)

* Removed unnecessary global variable (latent_entropy_plugin.c)
* About the latent_entropy gcc attribute (latent_entropy_plugin.c)
* Measure the boot time performance impact of the latent_entropy plugin
(arch/Kconfig)

---
Documentation/kernel-parameters.txt | 5 +
arch/Kconfig | 23 +

arch/powerpc/kernel/Makefile | 4 +
block/blk-softirq.c | 2 +-
drivers/char/random.c | 6 +-
fs/namespace.c | 1 +

include/linux/compiler-gcc.h | 7 +
include/linux/compiler.h | 4 +

include/linux/fdtable.h | 2 +-
include/linux/genhd.h | 2 +-

include/linux/init.h | 5 +-

include/linux/random.h | 14 +-
init/main.c | 1 +

kernel/fork.c | 7 +-

kernel/rcu/tiny.c | 2 +-
kernel/rcu/tree.c | 2 +-
kernel/sched/fair.c | 2 +-

kernel/softirq.c | 4 +-

kernel/time/timer.c | 2 +-
lib/irq_poll.c | 2 +-
lib/random32.c | 2 +-

mm/page_alloc.c | 31 ++
net/core/dev.c | 4 +-
scripts/Makefile.gcc-plugins | 10 +-
scripts/gcc-plugins/Makefile | 1 +
scripts/gcc-plugins/latent_entropy_plugin.c | 639 ++++++++++++++++++++++++++++
26 files changed, 760 insertions(+), 24 deletions(-)

[Emese Revfy]

This plugin mitigates the problem of the kernel having too little entropy
during and after boot for generating crypto keys.

It creates a local variable in every marked function. The value of
this variable is modified by randomly chosen operations (add, xor and rol)
and random values (gcc generates them at compile time and the stack pointer
at runtime).
It depends on the control flow (e.g., loops, conditions).

Before the function returns the plugin writes this local variable
into the latent_entropy global variable. The value of this global variable
is added to the kernel entropy pool in do_one_initcall() and _do_fork().

Signed-off-by: Emese Revfy <re.e...@gmail.com>

---
arch/Kconfig | 18 +
arch/powerpc/kernel/Makefile | 4 +

include/linux/random.h | 10 +
init/main.c | 1 +
kernel/fork.c | 1 +
mm/page_alloc.c | 5 +

scripts/Makefile.gcc-plugins | 8 +-

scripts/gcc-plugins/Makefile | 1 +
scripts/gcc-plugins/latent_entropy_plugin.c | 639 ++++++++++++++++++++++++++++

9 files changed, 686 insertions(+), 1 deletion(-)

create mode 100644 scripts/gcc-plugins/latent_entropy_plugin.c

diff --git a/arch/Kconfig b/arch/Kconfig

index 05f1e95..4b7cc2f 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -393,6 +393,24 @@ config GCC_PLUGIN_SANCOV

gcc-4.5 on). It is based on the commit "Add fuzzing coverage support"
by Dmitry Vyukov <dvy...@google.com>.

+config GCC_PLUGIN_LATENT_ENTROPY
+ bool "Generate some entropy during boot and runtime"
+ depends on GCC_PLUGINS
+ help
+ By saying Y here the kernel will instrument some kernel code to
+ extract some entropy from both original and artificially created
+ program state. This will help especially embedded systems where
+ there is little 'natural' source of entropy normally. The cost
+ is some slowdown of the boot process (about 0.5%) and fork and
+ irq processing.
+

+ Note that entropy extracted this way is not cryptographically

+ secure!
+
+ This plugin was ported from grsecurity/PaX. More information at:
+ * https://grsecurity.net/
+ * https://pax.grsecurity.net/
+
config HAVE_CC_STACKPROTECTOR
bool
help

diff --git a/arch/powerpc/kernel/Makefile b/arch/powerpc/kernel/Makefile
index 2da380f..01935b8 100644
--- a/arch/powerpc/kernel/Makefile
+++ b/arch/powerpc/kernel/Makefile
@@ -15,6 +15,10 @@ CFLAGS_btext.o += -fPIC
endif

ifdef CONFIG_FUNCTION_TRACER
+CFLAGS_cputable.o += $(DISABLE_LATENT_ENTROPY_PLUGIN)
+CFLAGS_init.o += $(DISABLE_LATENT_ENTROPY_PLUGIN)
+CFLAGS_btext.o += $(DISABLE_LATENT_ENTROPY_PLUGIN)
+CFLAGS_prom.o += $(DISABLE_LATENT_ENTROPY_PLUGIN)

# Do not trace early boot code

CFLAGS_REMOVE_cputable.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)
CFLAGS_REMOVE_prom_init.o = -mno-sched-epilog $(CC_FLAGS_FTRACE)

index 5c2c355..fd1b3c2 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1761,6 +1761,7 @@ long _do_fork(unsigned long clone_flags,

index 0000000..eb07b70
--- /dev/null
+++ b/scripts/gcc-plugins/latent_entropy_plugin.c
@@ -0,0 +1,639 @@

+ * void *local_entropy_frameaddr;

+ * // init_local_entropy() 3.

+ * unsigned long tmp_latent_entropy;

+ *
+ * // init_local_entropy() 2.

+ * local_entropy_frameaddr = __builtin_frame_address(0);
+ * local_entropy = (unsigned long) local_entropy_frameaddr;
+ *
+ * // init_local_entropy() 4.
+ * tmp_latent_entropy = latent_entropy;

+ * // init_local_entropy() 5.

+ * local_entropy ^= tmp_latent_entropy;

+ *
+ * // latent_entropy_execute() 3.
+ * local_entropy += 4623067384293424948;
+ *
+ * printf("%u %s\n", argc, *argv);
+ *
+ * // latent_entropy_execute() 4.

+ * tmp_latent_entropy = rol(tmp_latent_entropy, local_entropy);
+ * latent_entropy = tmp_latent_entropy;

+ .version = "201606141920vanilla",

+ .help = "disable\tturn off latent entropy instrumentation\n",
+};
+
+static unsigned HOST_WIDE_INT seed;
+/*
+ * get_random_seed() (this is a GCC function) generates the seed.
+ * This is a simple random generator without any cryptographic security because
+ * the entropy doesn't come from here.
+ */
+static unsigned HOST_WIDE_INT get_random_const(void)
+{
+ unsigned int i;
+ unsigned HOST_WIDE_INT ret = 0;
+

+ for (i = 0; i < 8 * sizeof(ret); i++) {

+ ret = (ret << 1) | (seed & 1);
+ seed >>= 1;
+ if (ret & 1)
+ seed ^= 0xD800000000000000ULL;
+ }
+
+ return ret;
+}
+
+static tree tree_get_random_const(tree type)
+{
+ unsigned long long mask;
+
+ mask = 1ULL << (TREE_INT_CST_LOW(TYPE_SIZE(type)) - 1);
+ mask = 2 * (mask - 1) + 1;
+
+ if (TYPE_UNSIGNED(type))
+ return build_int_cstu(type, mask & get_random_const());
+ return build_int_cst(type, mask & get_random_const());
+}
+
+static tree handle_latent_entropy_attribute(tree *node, tree name,

+ tree args __unused,
+ int flags __unused,
+ bool *no_add_attrs)

+{
+ tree type;
+#if BUILDING_GCC_VERSION <= 4007
+ VEC(constructor_elt, gc) *vals;
+#else

+ vec<constructor_elt, va_gc> *vals;

+#endif
+
+ switch (TREE_CODE(*node)) {
+ default:
+ *no_add_attrs = true;
+ error("%qE attribute only applies to functions and variables",

+ name);

+ break;
+
+ case VAR_DECL:
+ if (DECL_INITIAL(*node)) {
+ *no_add_attrs = true;

+ error("variable %qD with %qE attribute must not be initialized",

+ *node, name);

+ break;
+ }
+
+ if (!TREE_STATIC(*node)) {
+ *no_add_attrs = true;

+ error("variable %qD with %qE attribute must not be local",
+ *node, name);

+ break;
+ }
+
+ type = TREE_TYPE(*node);
+ switch (TREE_CODE(type)) {
+ default:
+ *no_add_attrs = true;

+ error("variable %qD with %qE attribute must be an integer or a fixed length integer array type or a fixed sized structure with integer fields",
+ *node, name);

+ break;
+
+ case RECORD_TYPE: {

+ tree fld, lst = TYPE_FIELDS(type);

+ unsigned int nelt = 0;
+

+ for (fld = lst; fld; nelt++, fld = TREE_CHAIN(fld)) {
+ tree fieldtype;
+
+ fieldtype = TREE_TYPE(fld);

+ if (TREE_CODE(fieldtype) == INTEGER_TYPE)
+ continue;
+
+ *no_add_attrs = true;

+ error("structure variable %qD with %qE attribute has a non-integer field %qE",
+ *node, name, fld);
+ break;
+ }
+
+ if (fld)

+ break;
+
+#if BUILDING_GCC_VERSION <= 4007
+ vals = VEC_alloc(constructor_elt, gc, nelt);
+#else
+ vec_alloc(vals, nelt);
+#endif
+

+ for (fld = lst; fld; fld = TREE_CHAIN(fld)) {
+ tree random_const, fld_t = TREE_TYPE(fld);
+
+ random_const = tree_get_random_const(fld_t);
+ CONSTRUCTOR_APPEND_ELT(vals, fld, random_const);

+ }
+
+ /* Initialize the fields with random constants */
+ DECL_INITIAL(*node) = build_constructor(type, vals);
+ break;
+ }
+
+ /* Initialize the variable with a random constant */
+ case INTEGER_TYPE:
+ DECL_INITIAL(*node) = tree_get_random_const(type);
+ break;
+
+ case ARRAY_TYPE: {
+ tree elt_type, array_size, elt_size;
+ unsigned int i, nelt;

+ HOST_WIDE_INT array_size_int, elt_size_int;

+
+ elt_type = TREE_TYPE(type);
+ elt_size = TYPE_SIZE_UNIT(TREE_TYPE(type));
+ array_size = TYPE_SIZE_UNIT(type);
+
+ if (TREE_CODE(elt_type) != INTEGER_TYPE || !array_size

+ || TREE_CODE(array_size) != INTEGER_CST) {
+ *no_add_attrs = true;
+ error("array variable %qD with %qE attribute must be a fixed length integer array type",
+ *node, name);
+ break;
+ }
+
+ array_size_int = TREE_INT_CST_LOW(array_size);
+ elt_size_int = TREE_INT_CST_LOW(elt_size);
+ nelt = array_size_int / elt_size_int;

+
+#if BUILDING_GCC_VERSION <= 4007
+ vals = VEC_alloc(constructor_elt, gc, nelt);
+#else
+ vec_alloc(vals, nelt);
+#endif
+

+ for (i = 0; i < nelt; i++) {

+ tree cst = size_int(i);
+ tree rand_cst = tree_get_random_const(elt_type);
+
+ CONSTRUCTOR_APPEND_ELT(vals, cst, rand_cst);
+ }
+
+ /*
+ * Initialize the elements of the array with random
+ * constants
+ */

+ tree list;

+
+ /* don't bother with noreturn functions for now */
+ if (TREE_THIS_VOLATILE(current_function_decl))
+ return false;
+
+ /* gcc-4.5 doesn't discover some trivial noreturn functions */
+ if (EDGE_COUNT(EXIT_BLOCK_PTR_FOR_FN(cfun)->preds) == 0)
+ return false;
+

+ list = DECL_ATTRIBUTES(current_function_decl);
+ return lookup_attribute("latent_entropy", list) != NULL_TREE;
+}
+
+static tree create_var(tree type, const char *name)

+static gimple create_assign(enum tree_code code, tree lhs, tree op1,
+ tree op2)
+{
+ return gimple_build_assign_with_ops(code, lhs, op1, op2);

+}
+
+static void perturb_local_entropy(basic_block bb, tree local_entropy)
+{
+ gimple_stmt_iterator gsi;
+ gimple assign;
+ tree rhs;
+ enum tree_code op;
+
+ op = get_op(&rhs);

+ assign = create_assign(op, local_entropy, local_entropy, rhs);

+ gsi = gsi_after_labels(bb);
+ gsi_insert_before(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+}
+
+static void __perturb_latent_entropy(gimple_stmt_iterator *gsi,

+ tree local_entropy)

+{
+ gimple assign;
+ tree temp;
+ enum tree_code op;
+
+ /* 1. create temporary copy of latent_entropy */

+ temp = create_var(unsigned_intDI_type_node, "tmp_latent_entropy");

+
+ /* 2. read... */
+ add_referenced_var(latent_entropy_decl);
+ mark_sym_for_renaming(latent_entropy_decl);
+ assign = gimple_build_assign(temp, latent_entropy_decl);
+ gsi_insert_before(gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+
+ /* 3. ...modify... */
+ op = get_op(NULL);

+ assign = create_assign(op, temp, temp, local_entropy);

+ tree frame_addr, rand_const, tmp, fndecl, udi_frame_addr;
+ enum tree_code op;
+ unsigned HOST_WIDE_INT rand_cst;

+ gimple_stmt_iterator gsi = gsi_after_labels(bb);
+

+ /* 1. create local_entropy_frameaddr */
+ frame_addr = create_var(ptr_type_node, "local_entropy_frameaddr");
+
+ /* 2. local_entropy_frameaddr = __builtin_frame_address() */

+ fndecl = builtin_decl_implicit(BUILT_IN_FRAME_ADDRESS);
+ call = gimple_build_call(fndecl, 1, integer_zero_node);
+ gimple_call_set_lhs(call, frame_addr);
+ gsi_insert_before(&gsi, call, GSI_NEW_STMT);
+ update_stmt(call);
+
+ udi_frame_addr = fold_convert(unsigned_intDI_type_node, frame_addr);
+ assign = gimple_build_assign(local_entropy, udi_frame_addr);
+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+
+ /* 3. create temporary copy of latent_entropy */

+ tmp = create_var(unsigned_intDI_type_node, "tmp_latent_entropy");

+
+ /* 4. read the global entropy variable into local entropy */
+ add_referenced_var(latent_entropy_decl);
+ mark_sym_for_renaming(latent_entropy_decl);

+ assign = gimple_build_assign(tmp, latent_entropy_decl);

+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+

+ /* 5. mix local_entropy_frameaddr into local entropy */
+ assign = create_assign(BIT_XOR_EXPR, local_entropy, local_entropy, tmp);

+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+

+ rand_cst = get_random_const();
+ rand_const = build_int_cstu(unsigned_intDI_type_node, rand_cst);
+ op = get_op(NULL);
+ assign = create_assign(op, local_entropy, local_entropy, rand_const);

+ gsi_insert_after(&gsi, assign, GSI_NEW_STMT);
+ update_stmt(assign);
+}
+
+static bool create_latent_entropy_decl(void)
+{
+ varpool_node_ptr node;
+
+ if (latent_entropy_decl != NULL_TREE)
+ return true;
+
+ FOR_EACH_VARIABLE(node) {

+ tree name, var = NODE_DECL(node);

+
+ if (DECL_NAME_LENGTH(var) < sizeof("latent_entropy") - 1)
+ continue;
+

+ name = DECL_NAME(var);
+ if (strcmp(IDENTIFIER_POINTER(name), "latent_entropy"))

+ local_entropy = create_var(unsigned_intDI_type_node, "local_entropy");

+
+ /* 2. initialize the local entropy variable */
+ init_local_entropy(bb, local_entropy);
+
+ bb = bb->next_bb;
+
+ /*

+ * 3. instrument each BB with an operation on the
+ * local entropy variable
+ */

+ while (bb != EXIT_BLOCK_PTR_FOR_FN(cfun)) {
+ perturb_local_entropy(bb, local_entropy);
+ bb = bb->next_bb;
+ };
+
+ /* 4. mix local entropy into the global entropy variable */
+ perturb_latent_entropy(local_entropy);
+ return 0;
+}
+
+static void latent_entropy_start_unit(void *gcc_data __unused,

+ void *user_data __unused)
+{
+ tree type, id;
+ int quals;

+
+ seed = get_random_seed(false);
+
+ if (in_lto_p)
+ return;
+
+ /* extern volatile u64 latent_entropy */
+ gcc_assert(TYPE_PRECISION(long_long_unsigned_type_node) == 64);

+ quals = TYPE_QUALS(long_long_unsigned_type_node) | TYPE_QUAL_VOLATILE;
+ type = build_qualified_type(long_long_unsigned_type_node, quals);
+ id = get_identifier("latent_entropy");
+ latent_entropy_decl = build_decl(UNKNOWN_LOCATION, VAR_DECL, id, type);

+
+ TREE_STATIC(latent_entropy_decl) = 1;
+ TREE_PUBLIC(latent_entropy_decl) = 1;
+ TREE_USED(latent_entropy_decl) = 1;
+ DECL_PRESERVE_P(latent_entropy_decl) = 1;
+ TREE_THIS_VOLATILE(latent_entropy_decl) = 1;
+ DECL_EXTERNAL(latent_entropy_decl) = 1;
+ DECL_ARTIFICIAL(latent_entropy_decl) = 1;
+ lang_hooks.decls.pushdecl(latent_entropy_decl);
+}
+
+#define PASS_NAME latent_entropy
+#define PROPERTIES_REQUIRED PROP_gimple_leh | PROP_cfg

+#define TODO_FLAGS_FINISH TODO_verify_ssa | TODO_verify_stmts | TODO_dump_func \
+ | TODO_update_ssa

+#include "gcc-generate-gimple-pass.h"
+
+int plugin_init(struct plugin_name_args *plugin_info,

+ struct plugin_gcc_version *version)

+ &latent_entropy_plugin_info);

+ if (enabled) {
+ register_callback(plugin_name, PLUGIN_START_UNIT,

+ &latent_entropy_start_unit, NULL);
+ register_callback(plugin_name, PLUGIN_REGISTER_GGC_ROOTS,
+ NULL, (void *)&gt_ggc_r_gt_latent_entropy);
+ register_callback(plugin_name, PLUGIN_PASS_MANAGER_SETUP, NULL,
+ &latent_entropy_pass_info);

+ }
+ register_callback(plugin_name, PLUGIN_ATTRIBUTES, register_attributes,

+ NULL);

[Emese Revfy]

The latent_entropy gcc attribute can be only on functions and variables.

If it is on a function then the plugin will instrument it. If the attribute

is on a variable then the plugin will initialize it with a random value.

The variable must be an integer, an integer array type or a structure

with integer fields.

These functions have been selected because they are init functions or
are called at random times or they have variable loops.

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

block/blk-softirq.c | 2 +-
drivers/char/random.c | 6 +++---
fs/namespace.c | 1 +
include/linux/compiler-gcc.h | 7 +++++++
include/linux/compiler.h | 4 ++++

include/linux/fdtable.h | 2 +-
include/linux/genhd.h | 2 +-

include/linux/init.h | 5 +++--
include/linux/random.h | 4 ++--
kernel/fork.c | 6 ++++--

kernel/rcu/tiny.c | 2 +-
kernel/rcu/tree.c | 2 +-
kernel/sched/fair.c | 2 +-

kernel/softirq.c | 4 ++--

kernel/time/timer.c | 2 +-
lib/irq_poll.c | 2 +-
lib/random32.c | 2 +-

mm/page_alloc.c | 2 +-
net/core/dev.c | 4 ++--

19 files changed, 38 insertions(+), 23 deletions(-)

index 4fb1691..0951eca 100644
--- a/fs/namespace.c
+++ b/fs/namespace.c
@@ -2778,6 +2778,7 @@ static struct mnt_namespace *alloc_mnt_ns(struct user_namespace *user_ns)
return new_ns;
}

+__latent_entropy
struct mnt_namespace *copy_mnt_ns(unsigned long flags, struct mnt_namespace *ns,
struct user_namespace *user_ns, struct fs_struct *new_fs)
{

index aedb254..88646cb 100644

--- a/include/linux/init.h
+++ b/include/linux/init.h
@@ -39,7 +39,7 @@

/* These are for everybody (although not all archs will actually
discard it in modules) */
-#define __init __section(.init.text) __cold notrace

+#define __init __section(.init.text) __cold notrace __latent_entropy

#define __initdata __section(.init.data)
#define __initconst __constsection(.init.rodata)
#define __exitdata __section(.exit.data)

@@ -92,7 +92,8 @@

#define __exit __section(.exit.text) __exitused __cold notrace

/* Used for MEMORY_HOTPLUG */
-#define __meminit __section(.meminit.text) __cold notrace

+#define __meminit __section(.meminit.text) __cold notrace \
+ __latent_entropy

#define __meminitdata __section(.meminit.data)
#define __meminitconst __constsection(.meminit.rodata)
#define __memexit __section(.memexit.text) __exitused __cold notrace

diff --git a/include/linux/random.h b/include/linux/random.h
index 752e7df..d286d51 100644
--- a/include/linux/random.h
+++ b/include/linux/random.h

@@ -29,8 +29,8 @@ static inline void add_latent_entropy(void) {}
#endif

extern void add_input_randomness(unsigned int type, unsigned int code,

- unsigned int value);
-extern void add_interrupt_randomness(int irq, int irq_flags);
+ unsigned int value) __latent_entropy;
+extern void add_interrupt_randomness(int irq, int irq_flags) __latent_entropy;

extern void get_random_bytes(void *buf, int nbytes);
extern int add_random_ready_callback(struct random_ready_callback *rdy);

diff --git a/kernel/fork.c b/kernel/fork.c
index fd1b3c2..8b1e313 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -406,7 +406,8 @@ free_tsk:
}

#ifdef CONFIG_MMU
-static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)

+static __latent_entropy int dup_mmap(struct mm_struct *mm,

+ struct mm_struct *oldmm)

{
struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
struct rb_node **rb_link, *rb_parent;

@@ -1277,7 +1278,8 @@ init_task_pid(struct task_struct *task, enum pid_type type, struct pid *pid)

* parts of the process environment (as per the clone
* flags). The actual kick-off is left to the caller.
*/
-static struct task_struct *copy_process(unsigned long clone_flags,
+static __latent_entropy struct task_struct *copy_process(

+ unsigned long clone_flags,

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index d10324e..ffc4f4a 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c

[Emese Revfy]

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

scripts/Makefile.gcc-plugins | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/scripts/Makefile.gcc-plugins b/scripts/Makefile.gcc-plugins
index 5e22b60..da7f86c 100644
--- a/scripts/Makefile.gcc-plugins
+++ b/scripts/Makefile.gcc-plugins

@@ -19,7 +19,7 @@ ifdef CONFIG_GCC_PLUGINS
endif
endif

- GCC_PLUGINS_CFLAGS := $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y))

+ GCC_PLUGINS_CFLAGS := $(strip $(addprefix -fplugin=$(objtree)/scripts/gcc-plugins/, $(gcc-plugin-y)) $(gcc-plugin-cflags-y))

export PLUGINCC GCC_PLUGINS_CFLAGS GCC_PLUGIN SANCOV_PLUGIN

--
2.8.1

[Emese Revfy]

When extra_latent_entropy is passed on the kernel command line,
entropy will be extracted from up to the first 4GB of RAM while the
runtime memory allocator is being initialized.

Based on work created by the PaX Team.

Signed-off-by: Emese Revfy <re.e...@gmail.com>
---

Documentation/kernel-parameters.txt | 5 +++++
arch/Kconfig | 5 +++++
mm/page_alloc.c | 26 ++++++++++++++++++++++++++
3 files changed, 36 insertions(+)

diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt
index 82b42c9..d870702 100644
--- a/Documentation/kernel-parameters.txt
+++ b/Documentation/kernel-parameters.txt
@@ -2862,6 +2862,11 @@ bytes respectively. Such letter suffixes can also be entirely omitted.
the specified number of seconds. This is to be used if
your oopses keep scrolling off the screen.

+ extra_latent_entropy
+ Enable a very simple form of latent entropy extraction
+ from the first 4GB of memory as the bootmem allocator
+ passes the memory pages to the buddy allocator.
+
pcbit= [HW,ISDN]

pcd. [PARIDE]
diff --git a/arch/Kconfig b/arch/Kconfig
index 4b7cc2f..3374d50 100644
--- a/arch/Kconfig
+++ b/arch/Kconfig
@@ -404,6 +404,11 @@ config GCC_PLUGIN_LATENT_ENTROPY

is some slowdown of the boot process (about 0.5%) and fork and

irq processing.

+ When extra_latent_entropy is passed on the kernel command line,
+ entropy will be extracted from up to the first 4GB of RAM while the
+ runtime memory allocator is being initialized. This costs even more
+ slowdown of the boot process.

+
Note that entropy extracted this way is not cryptographically

secure!

diff --git a/mm/page_alloc.c b/mm/page_alloc.c
index ffc4f4a..0a40c12 100644
--- a/mm/page_alloc.c
+++ b/mm/page_alloc.c
@@ -63,6 +63,7 @@
#include <linux/sched/rt.h>
#include <linux/page_owner.h>
#include <linux/kthread.h>
+#include <linux/random.h>

#include <asm/sections.h>
#include <asm/tlbflush.h>
@@ -1234,6 +1235,15 @@ static void __free_pages_ok(struct page *page, unsigned int order)
local_irq_restore(flags);
}

+bool __meminitdata extra_latent_entropy;
+
+static int __init setup_extra_latent_entropy(char *str)
+{
+ extra_latent_entropy = true;
+ return 0;
+}
+early_param("extra_latent_entropy", setup_extra_latent_entropy);
+
#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
volatile u64 latent_entropy __latent_entropy;
EXPORT_SYMBOL(latent_entropy);
@@ -1254,6 +1264,22 @@ static void __init __free_pages_boot_core(struct page *page, unsigned int order)
__ClearPageReserved(p);
set_page_count(p, 0);

+ if (extra_latent_entropy && !PageHighMem(page) &&
+ page_to_pfn(page) < 0x100000) {
+ u64 hash = 0;
+ size_t index, end = PAGE_SIZE * nr_pages / sizeof(hash);
+ const u64 *data = lowmem_page_address(page);
+
+ for (index = 0; index < end; index++)
+ hash ^= hash + data[index];
+#ifdef CONFIG_GCC_PLUGIN_LATENT_ENTROPY
+ latent_entropy ^= hash;

+ add_device_randomness((const void *)&latent_entropy, sizeof(latent_entropy));

+#else
+ add_device_randomness((const void *)&hash, sizeof(hash));
+#endif
+ }
+
page_zone(page)->managed_pages += nr_pages;
set_page_refcounted(page);
__free_pages(page, order);
--
2.8.1

[Christoph Hellwig]

On Mon, Jun 20, 2016 at 08:41:19PM +0200, Emese Revfy wrote:
> --- /dev/null
> +++ b/scripts/gcc-plugins/latent_entropy_plugin.c
> @@ -0,0 +1,639 @@
> +/*
> + * Copyright 2012-2016 by the PaX Team <page...@freemail.hu>
> + * Copyright 2016 by Emese Revfy <re.e...@gmail.com>
> + * Licensed under the GPL v2
> + *
> + * Note: the choice of the license means that the compilation process is
> + * NOT 'eligible' as defined by gcc's library exception to the GPL v3,
> + * but for the kernel it doesn't matter since it doesn't link against
> + * any of the gcc libraries

I remember we used to have architectures that actually linked against
libgcc. Isn't that the case anymore?

[Kees Cook]

There are a few, but they don't (and won't) select HAVE_GCC_PLUGINS.

[Kees Cook]

On Mon, Jun 20, 2016 at 11:39 AM, Emese Revfy <re.e...@gmail.com> wrote:
> I would like to introduce the latent_entropy gcc plugin. This plugin
> mitigates the problem of the kernel having too little entropy during and
> after boot for generating crypto keys.
>
> This plugin mixes random values into the latent_entropy global variable
> in functions marked by the __latent_entropy attribute.
> The value of this global variable is added to the kernel entropy pool
> to increase the entropy.
>
> It is a CII project supported by the Linux Foundation.
>
> The latent_entropy plugin was ported from grsecurity/PaX originally written
> by the PaX Team. You can find more about the plugin here:
> https://grsecurity.net/pipermail/grsecurity/2012-July/001093.html
>
> The plugin supports all gcc version from 4.5 to 6.0.
>
> I do some changes above the PaX version. The important one is mixing
> the stack pointer into the global variable too.
> You can find more about the changes here:
> https://github.com/ephox-gcc-plugins/latent_entropy
>
> This patch set is based on the "Introduce GCC plugin infrastructure"
> patch set (git/mmarek/kbuild.git#kbuild HEAD: 543c37cb165049c3be).
>
> Emese Revfy (4):
> Add support for passing gcc plugin arguments
> Add the latent_entropy gcc plugin
> Mark functions with the latent_entropy attribute
> Add the extra_latent_entropy kernel parameter

Thanks! This looks good to me. I've adjusted some of the commit
message language for clarity and fixed a few other >80 lines that
stood out to me.

I've applied this to for-next/kspp and after I finish local build
testing, it should appear in linux-next.

Yay! :)