Skip to content
GitHub no longer supports this web browser. Learn more about the browsers we support.
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Timing of block downloads leaks whether or not any notes belonging to the wallet were discovered #95

Open
defuse opened this issue Jan 16, 2020 · 7 comments
Assignees

Comments

@defuse
Copy link
Contributor

@defuse defuse commented Jan 16, 2020

This issue was originally discovered and reported by Florian Tramèr. I'm making it public since no users are currently at risk.

The issue is that the SDK will:

  1. Download new blocks,
  2. process those blocks, taking an amount of time that depends on how many notes belong to this wallet,
  3. wait a fixed length of time,
  4. make a request to lightwalletd for more new blocks.

A passive network adversary can measure the time between (1) and (4) to determine whether any notes in the blocks belonged to the wallet. To fix this, either

a. Decouple the network code from the block processing code, such that downloaded blocks are queued up to be processed on a separate thread and the processing won't affect the timing of network requests,
b. Florian's suggestion, to request blocks at absolute time intervals, i.e. instead of sleeping for 20 seconds between requests, request new blocks at times *:00, *:20, *:40. In order for this to not leak information, the block processing MUST always complete before the next request is due to be made.

I recommend (b) since it's easier and we're about to run into even harder side-channel challenges with memo downloading and mempool access.

@gmale

This comment has been minimized.

Copy link
Collaborator

@gmale gmale commented Jan 17, 2020

Until we change the way data access works, I'm concerned about option A because it could lead to concurrent access of the SQLite file holding the cached blocks.

Since the Rust side of the logic (scanning) and the Kotlin side both use the *.db file and a write occuring at the same time as a read leads to "corrupt database" errors, it has been safer to keep all DB access sequential.

I'd also like to detect blocks as soon as possible after their availability. Would random time be acceptable? Perhaps with some fixed minimum? I'm thinking at least 10 but up to blocktime/2 seconds.

So instead of:

delay(FIXED_TIME)

We'd use something like:

delay(FIXED_TIME + Random.nextInt(FIXED_TIME))

Where FIXED_TIME is around 20 seconds or so.

@defuse thoughts?

@ftramer

This comment has been minimized.

Copy link

@ftramer ftramer commented Jan 17, 2020

I wouldn't recommend the randomized delay approach, due to the following attack:
Say the adversary obtains a public key and wants to know if this key belongs to a certain mobile user. The adversary can create many payments for this public key (even payments of 0 value work), and then time the SDK's delay when processing each of them. This averages out the randomized delay and reveals the delay incurred when processing a payment.

gmale added a commit that referenced this issue Jan 17, 2020
Addresses #95
@gmale

This comment has been minimized.

Copy link
Collaborator

@gmale gmale commented Jan 17, 2020

Thank you for the feedback @ftramer this information is very helpful! I'd like to implement changes immediately but I have some questions, to help me understand this correctly:

and then time the SDK's delay when processing each of them

  1. How might this work in practice on a mobile device?

In our current implementation, the app only downloads blocks while the app is in the foreground. So the attacker would have to 0) know the suspected address of their target 1) catch the target actively using the app 2) either be on the same network, intercepting TLS communications, or have fully compromised the lightwalletd server 3) send many payments across many blocks in order to average out the random delay (it seems like it would take a LOT of payments to do this) 4) and possibly be able to distinguish the other potential sources of timing delays on the mobile device (like switching apps, receiving a phone call or a text or doing other background processing in that thread pool)--which I think just increases the amount of blocks required to pull this off.

Does that sound about right or is the attack easier than this?

Overall, it seems reasonable to do both things: request blocks on time boundaries and ALSO add some random jitter as one additional obstacle to timing attacks, which might also help Lightwalletd servers have a more balanced distribution of requests.

@gmale gmale self-assigned this Jan 17, 2020
@ftramer

This comment has been minimized.

Copy link

@ftramer ftramer commented Jan 17, 2020

Yes this attack model assumes either a compromised lightwalletd or a network adversary that can passively observe the communication between the mobile device and lightwalletd (e.g., an ISP).

I agree that the averaging attack might need many blocks to obtain a reliable signal. This depends on how much longer the transaction processing takes when the wallet is the payee. On my desktop machine, the delay is a few milliseconds. On a weak mobile device it could be much larger.
An adversary could also include many transactions with the same payment address in a single block. This way, you amplify the delay caused by payment processing but only have a single randomized delay at the end of the block.

Ultimately, it just seems that requesting blocks on fixed time boundaries is arguably not too complicated and a more private approach than using jitter. Of course combining the two cannot hurt.

gmale added a commit that referenced this issue Jan 17, 2020
Addresses #95
@daira

This comment has been minimized.

Copy link

@daira daira commented Jan 30, 2020

The delay introduced by the current code is always a multiple of 1 millisecond. Does this still leak a small amount of timing information?

@zebambam

This comment has been minimized.

Copy link

@zebambam zebambam commented Jan 30, 2020

It's conceivable that network and other load delay would be sufficient to kill the hundreds of microseconds delay leakage, assuming that the oracle is network-based and not local. I think that's probably a safe assumption on mobile in a practical sense, but it's also something that we could revisit later on.

@zebambam

This comment has been minimized.

Copy link

@zebambam zebambam commented Jan 30, 2020

Of course ideally we would just decouple network and wallet operations completely.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
5 participants
You can’t perform that action at this time.