Project

General

Profile

Feature #7675

Persist entropy pool seeds

Added by intrigeri over 3 years ago. Updated 17 days ago.

Status:
Confirmed
Priority:
Normal
Assignee:
Category:
Persistence
Target version:
Start date:
11/04/2016
Due date:
% Done:

10%

QA Check:
Info Needed
Feature Branch:
Type of work:
Code

Description

As a Tails user
When I boot Tails with persistence enabled
Then when an entropy is required, it would use the entropy pool seed

Rationale

Generating entropy on a live distribution is a tough problem. And this has impact to securely generate cryptographic keys, like for example for Pidgin-OTR, using SSH or generating a PGP key. We hope to improve this situation for users who enable the persistence storage option using some randomness from the previous session to help bootstrap with some "well" generated randomness.

Technical discussion

From the discussions and research on #7642 and #5650, it seems clear that it would be good to persist entropy pool seeds (/var/lib/random-seed, /var/lib/urandom/random-seed, /var/lib/systemd/random-seed, etc.) whenever possible.

It might even be that we want to do that by default when persistence is enabled (although it's a hard decision to make, because it breaks one of the basic assumptions of how Tails works).

Still, note that these seeds won't be used at early boot stage, but only once persistence is enabled. We should look at pointers on #6116 and evaluate how much of a problem it is in practice, in Tails use case.

Team

Team: segfault, bertagaz


Subtasks

Feature #11898: Have a readable blueprint about randomness in TailsIn ProgressDr_Whax


Related issues

Related to Tails - Feature #7642: Investigate whether we should resume shipping a static random seed In Progress 09/02/2016
Related to Tails - Feature #5650: rngd Resolved
Related to Tails - Feature #7646: Investigate whether we should ship /var/lib/systemd/random-seed Duplicate 07/23/2014
Related to Tails - Feature #6116: Audit random seed Confirmed

History

#1 Updated by intrigeri over 3 years ago

  • Related to Feature #7642: Investigate whether we should resume shipping a static random seed added

#2 Updated by intrigeri over 3 years ago

#3 Updated by intrigeri over 3 years ago

  • Related to Feature #7646: Investigate whether we should ship /var/lib/systemd/random-seed added

#4 Updated by intrigeri over 3 years ago

#5 Updated by intrigeri over 3 years ago

  • Description updated (diff)

#6 Updated by intrigeri almost 3 years ago

  • Assignee set to intrigeri
  • Target version set to Tails_1.4

I'll try to work on it for Tails 1.4.

#7 Updated by intrigeri over 2 years ago

  • Target version changed from Tails_1.4 to Hole in the Roof

#8 Updated by sycamoreone over 2 years ago

I once promised to ask around about this issue and got directed to the randomness-generation mailing list.

I asked a question there, but only little feedback.

#9 Updated by intrigeri over 2 years ago

  • Assignee deleted (intrigeri)

#10 Updated by Dr_Whax over 2 years ago

  • Assignee set to Dr_Whax

I'll lead the discussion with a couple of cryptographers so we can come up with a plan to integrate it.

#11 Updated by emmapeel over 2 years ago

Dr_Whax wrote:

I'll lead the discussion with a couple of cryptographers so we can come up with a plan to integrate it.

During yesterday's contributors meeting1, sycamoreone said that was iinterested on this, so maybe he wants to join that conversation.

[1] https://tails.boum.org/contribute/meetings/201508/

#12 Updated by sajolida over 2 years ago

  • Description updated (diff)
  • Assignee changed from Dr_Whax to bertagaz

#13 Updated by Dr_Whax about 2 years ago

  • Description updated (diff)

#14 Updated by Dr_Whax about 2 years ago

  • Description updated (diff)

#15 Updated by intrigeri almost 2 years ago

  • Blueprint set to https://tails.boum.org/blueprint/randomness_seeding/

#16 Updated by intrigeri almost 2 years ago

One (crazy?) option could be to store a device-specific seed in the attributes bits of the Tails system partition's GPT entry. IIRC there are 16 bits there we could use (but better reserve a few of them for future uses). This way, even without persistence one might get something better than what we currently have. Whether we want to update this seed on the drive during boot and/or shutdown, when the persistence is enabled/disabled, is left as an exercise for the reader :) Now, if we're ready to do that, of course we can as well have Tails Installer put the seed inside the system partition, if it's more practical. But it may be harder to update it.

#17 Updated by sajolida almost 2 years ago

Just to understand better the proposal: what would be the advantages of using the GPT partition table over storing it in a file on the system partition?

#18 Updated by intrigeri almost 2 years ago

Just to understand better the proposal: what would be the advantages of using the GPT partition table over storing it in a file on the system partition?

No idea yet :)

#19 Updated by intrigeri over 1 year ago

So, kurono posted another implementation idea to the blueprint (use Tails Installer), and dgoulet + sycamoreone had yet another idea (#5650#note-21): "query the amount of entropy added to the pool. It would be possible to start both services [haveged and rngd] early in the boot process and then block until enough entropy is available. We then wouldn't need to var/.../random-seed files".

#20 Updated by cypherpunks over 1 year ago

intrigeri wrote:

One (crazy?) option could be to store a device-specific seed in the attributes bits of the Tails system partition's GPT entry. IIRC there are 16 bits there we could use (but better reserve a few of them for future uses). This way, even without persistence one might get something better than what we currently have. Whether we want to update this seed on the drive during boot and/or shutdown, when the persistence is enabled/disabled, is left as an exercise for the reader :) Now, if we're ready to do that, of course we can as well have Tails Installer put the seed inside the system partition, if it's more practical. But it may be harder to update it.

16 bits is pretty useless for randomness... That's a keyspace of just 65536. Considering the system already gets randomness from things like the MAC address and other hardware, I think that would just add unnecessary complexity without any benefit. Now, there should be plenty of room in the MBRs (both the backup and main). I wonder how much entropy could be added by exploiting redundancy in the x86 instruction set... You could probably modify the executable on the fly at each boot, replacing each opcode for an equivalently functional but different one. I don't know much about GPT (I only use MBR myself) other than that they have two backup MBRs, but I assume those backup MBRs are still executable? Either way, there'd be plenty of room for at least 128 bits of persistent data, whether in stego-style x86 opcode redundancy, or just unused space between various places.

Or hell, just change the UUID at each boot. :P

#21 Updated by cypherpunks over 1 year ago

cypherpunks wrote:

Now, there should be plenty of room in the MBRs (both the backup and main). I wonder how much entropy could be added by exploiting redundancy in the x86 instruction set... You could probably modify the executable on the fly at each boot, replacing each opcode for an equivalently functional but different one.

Each MBR contains up to 446 bytes of executable code (though typically only 436 bytes are used). The best method of exploiting x86 redundancy that I know of is Hydan, with 1/110 for an encoding efficiency. 446 * 2 / 110 * 8 ~= 65, so only about 65 bits could be stored in two MBRs. Not quite enough for a cryptographic seed.

Would it be appreciated if I created a PoC which stored persistent seeds between the end of the executable code in each MBR and the beginning of the UUID and partition table data, which should contain 80 bits each? Or alternatively (and more easily), have it stored on the system partition? The only downside I see to having it stored on the system partition are for people who like to checksum their drive before they boot it. It's much easier to ignore changes to GPT areas than it is to ignore filesystem changes (which extend to metadata entries far beyond a set offset at the beginning of the drive). Other than that, storing it on the FAT32 filesystem is certainly easier to do and less prone to accidents.

#22 Updated by intrigeri over 1 year ago

Other than that, storing it on the FAT32 filesystem is certainly easier to do and less prone to accidents.

+1

#23 Updated by Dr_Whax over 1 year ago

  • Description updated (diff)
  • Target version changed from Hole in the Roof to 2017

#24 Updated by bertagaz about 1 year ago

  • Type of work changed from Research to Code

At the November 4th meeting, we decided that this was a ticket we could start to work on.

We also decided to ask to tickets' assignee to write down a small presentation of the goal of their ticket, to be included in the blueprint that we'll show publicly. So it needs to be clear the ticket is about, what it will implement and why. There's already bits written in the blueprint dedicated paragraph, but it probably needs to be clarified for external readers. Please check and enhance it!

#25 Updated by intrigeri 8 months ago

DrWhax, bertagaz, sycamoreone: this topic seems to be stalled since November; perhaps it's time to make it clear what the next step is, and who committed to make it happen?

#26 Updated by bertagaz 8 months ago

  • Assignee changed from bertagaz to Dr_Whax
  • QA Check set to Info Needed

intrigeri wrote:

DrWhax, bertagaz, sycamoreone: this topic seems to be stalled since November; perhaps it's time to make it clear what the next step is, and who committed to make it happen?

Right. IIRC, we were at the state where we considered this blueprint ready to be reviewed.

We wanted to have it reviewed internally, during a monthly meeting. Now I think we should have this discussion on the tails-dev mailing list, that would really ease the discussion. DrWhax, what's you opinion on that? Are you interested to take care of this discussion?

We also wanted to have feedbacks from external skillful people. We wanted to catch that kind of people during the last CCC, I don't know if it happened. DrWhax, care to give a feedback about that if any? Maybe it didn't happen in the end because we didn't have any internal review. But then we can still send some emails once this internal review has been done.

Assigning to Dr_Whax to have feedbacks on this questions. Please re-assign to me if you prefer that I take care of the discussion on tails-dev.

#27 Updated by u 6 months ago

Ping @drwhax, see previous comment for open questions please :)

#28 Updated by intrigeri 4 months ago

Linux will soon support adding the kernel command line as a source of randomness. One of the corresponding commit messages explains how Android uses this. I bet that'll be the best way for us to go as it triggers much earlier than anything we can do in userspace. Next step: check how this can be integrated into our syslinux config and install/upgrade process.

#29 Updated by BitingBird 4 months ago

  • Description updated (diff)
  • Assignee changed from Dr_Whax to segfault
  • Target version changed from 2017 to 2019

#30 Updated by intrigeri 3 months ago

intrigeri wrote:

Linux will soon support adding the kernel command line as a source of randomness. One of the corresponding commit messages explains how Android uses this.

… except this was broken initially. It's fixed in Linux 4.13 (security things in Linux v4.13, commit).

#31 Updated by intrigeri 3 months ago

  • Target version changed from 2019 to 2018

(as per updated roadmap)

#32 Updated by intrigeri 17 days ago

intrigeri wrote:

intrigeri wrote:

Linux will soon support adding the kernel command line as a source of randomness. One of the corresponding commit messages explains how Android uses this.

… except this was broken initially. It's fixed in Linux 4.13 (security things in Linux v4.13, commit).

… and improved in Linux 4.14.

Also available in: Atom PDF