Oh, Jeeez...!

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
28 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Oh, Jeeez...!

Kiss Gabor (Bitman)
Guys,

Have you remembered I'm continuosly worrying about
trolls pumping 10-20 millions of dummy keys into key servers?
It is started...

http://keys.niif.hu/pks/lookup?op=vindex&search=0x0B7F8B60E3EDFAE3
(Scroll over the whole page.)

So we must hard think how to delete keys/signatures.

Gabor

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Tobias Frei

Hi,

to be honest, it somehow makes me happy that we're finally being forced to find a solution for this. It could have started worse.

I think the only reasonable solution is that every server operator gets a local blacklist that can be filled with keys / signatures / regex etc. and that only prevents matched entries from being saved to the database. To remove a key from all servers, all operators would need to add it to the blacklist then. This prevents abuse of the mechanism while giving easy, effective control over the own database to every server operator.

We could then discuss or suggest entries for the blacklist that everyone should add, but it would be the responsibility and choice of every admin to follow the suggestions.

Best regards,
Tobias Frei


On Tue, May 24, 2016, 06:34 Kiss Gabor (Bitman) <[hidden email]> wrote:
Guys,

Have you remembered I'm continuosly worrying about
trolls pumping 10-20 millions of dummy keys into key servers?
It is started...

http://keys.niif.hu/pks/lookup?op=vindex&search=0x0B7F8B60E3EDFAE3
(Scroll over the whole page.)

So we must hard think how to delete keys/signatures.

Gabor

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Sven Kocksch
Zitat von Tobias Frei <[hidden email]>:

> Hi,
>
> to be honest, it somehow makes me happy that we're finally being forced to
> find a solution for this. It could have started worse.
>
> I think the only reasonable solution is that every server operator gets a
> local blacklist that can be filled with keys / signatures / regex etc. and
> that only prevents matched entries from being saved to the database. To
> remove a key from all servers, all operators would need to add it to the
> blacklist then. This prevents abuse of the mechanism while giving easy,
> effective control over the own database to every server operator.
>
> We could then discuss or suggest entries for the blacklist that everyone
> should add, but it would be the responsibility and choice of every admin to
> follow the suggestions.
>
> Best regards,
> Tobias Frei
>
> On Tue, May 24, 2016, 06:34 Kiss Gabor (Bitman) <[hidden email]> wrote:
>
>> Guys,
>>
>> Have you remembered I'm continuosly worrying about
>> trolls pumping 10-20 millions of dummy keys into key servers?
>> It is started...
>>
>> http://keys.niif.hu/pks/lookup?op=vindex&search=0x0B7F8B60E3EDFAE3
>> (Scroll over the whole page.)
>>
>> So we must hard think how to delete keys/signatures.
>>
>> Gabor
>>
>> _______________________________________________
>> Sks-devel mailing list
>> [hidden email]
>> https://lists.nongnu.org/mailman/listinfo/sks-devel
>>
Hello Tobias,

If a server rejects large amounts of keys wouldn't it fall out of the  
pool because of missing keys?
(Given that a good portion of the servers in the pool still accept  
these keys and so the average number of keys is higher than yours)


Greetings
Sven

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

attachment0 (501 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Kiss Gabor (Bitman)
In reply to this post by Tobias Frei
> I think the only reasonable solution is that every server operator gets a
> local blacklist that can be filled with keys / signatures / regex etc. and
> that only prevents matched entries from being saved to the database. To
> remove a key from all servers, all operators would need to add it to the
> blacklist then. This prevents abuse of the mechanism while giving easy,
> effective control over the own database to every server operator.
>
> We could then discuss or suggest entries for the blacklist that everyone
> should add, but it would be the responsibility and choice of every admin to
> follow the suggestions.

In theory it could work.
However we should have maintain such a large blacklist
as the whole database.
The story reminds me Google's automated deletion system.
It gets zillion requests a day.

Another idea: database must have a version number.
Key servers holding the same version may exchange keys unrestricted.
Different version servers exchange keys according to certain rules.
Every year or so we create a new cleaned version of database
and it gets a new version number.
So we don't need an endless growing blacklist. We select valuable
keys from the old (poisoned) version of the database into the new.
Then the new one becames the etalon that should reach every server.

Gabor

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Pascal Levasseur-2
In reply to this post by Kiss Gabor (Bitman)
Le 24/05/2016 06:33, Kiss Gabor (Bitman) a écrit :

> Guys,
>
> Have you remembered I'm continuosly worrying about
> trolls pumping 10-20 millions of dummy keys into key servers?
> It is started...
>
> http://keys.niif.hu/pks/lookup?op=vindex&search=0x0B7F8B60E3EDFAE3
> (Scroll over the whole page.)
>
> So we must hard think how to delete keys/signatures.
>
> Gabor
>
> _______________________________________________
> Sks-devel mailing list
> [hidden email]
> https://lists.nongnu.org/mailman/listinfo/sks-devel
>
Can we add a proof of work mechanism to make adding a key to the server
more "costly" ?.

Pascal


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Tobias Frei
Hi,

Adding proof of work can only prevent an attack that depends on a huge number of useless keys. Someone else once mentioned that a single key with an illegal image ID can already cause huge problems, and deleting such a key can become the only way to be legally allowed to continue running a keyserver.

About lacking keys, well, if the pool selection mechanism causes working keyservers to be removed, that's a separate problem that needs to be solved after this one, I think. It should not be an argument for or against this suggestion, but instead needs to adapt to the current situation.

Best regards,
Tobias Frei

(sorry, I accidentally sent this as direct reply instead of list reply before) 

On Tue, May 24, 2016, 17:00 Pascal Levasseur <[hidden email]> wrote:
Le 24/05/2016 06:33, Kiss Gabor (Bitman) a écrit :
> Guys,
>
> Have you remembered I'm continuosly worrying about
> trolls pumping 10-20 millions of dummy keys into key servers?
> It is started...
>
> http://keys.niif.hu/pks/lookup?op=vindex&search=0x0B7F8B60E3EDFAE3
> (Scroll over the whole page.)
>
> So we must hard think how to delete keys/signatures.
>
> Gabor
>
> _______________________________________________
> Sks-devel mailing list
> [hidden email]
> https://lists.nongnu.org/mailman/listinfo/sks-devel
>

Can we add a proof of work mechanism to make adding a key to the server
more "costly" ?.

Pascal

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Christoph Egger-9
Tobias Frei <[hidden email]> writes:
> About lacking keys, well, if the pool selection mechanism causes
> working keyservers to be removed, that's a separate problem that needs
> to be solved after this one, I think. It should not be an argument for
> or against this suggestion, but instead needs to adapt to the current
> situation.

It's not only pool selection but also at the very core of how the recon
protocol works. You can't fix that as an afterthought.

  Christoph

--
9FED 5C6C E206 B70A 5857  70CA 9655 22B9 D49A E731
Debian Developer | Lisp Hacker | CaCert Assurer

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Arnold-27
In reply to this post by Tobias Frei
On 24-05-16 18:17, Tobias Frei wrote:
> Adding proof of work can only prevent an attack that depends on a huge number of
> useless keys.

Setting a maximum upload size can help and is easy to implement locally. Further,
it is possible to limit the rate at which a single IP (or IPv6/64) can upload new
or updated keys.

> Someone else once mentioned that a single key with an illegal image
> ID can already cause huge problems, and deleting such a key can become the only way
> to be legally allowed to continue running a keyserver.

A possible solution I suggested a while ago is to have SKS synchronize only a
subset of the database. The Set Theory that SKS uses, can be applied to subsets all
the same. All we need is a good definition of the subset(s).

If we agree to synchronise only the keys modified in the last three months or so,
then everyone has the option to locally(!) delete keys that have not been modified
for some time. Right now we ask new operators to have a recent dump before we start
peering anyway. Yaron thought something like this is "totally doable" (see his
e-mail of  21 May 2015 21:16:36 +0000), but it needs work...


> About lacking keys, well, if the pool selection mechanism causes working keyservers
> to be removed, that's a separate problem that needs to be solved after this one, I
> think. It should not be an argument for or against this suggestion, but instead
> needs to adapt to the current situation.

I guess the stats of SKS can be modified to show more stats, like the number of
keys in the subset that is being synchronised.

Arnold

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Chris Morrow
At Wed, 25 May 2016 00:04:05 +0200,
Arnold wrote:
>
> On 24-05-16 18:17, Tobias Frei wrote:
> > Adding proof of work can only prevent an attack that depends on a huge number of
> > useless keys.
>
> Setting a maximum upload size can help and is easy to implement locally. Further,
> it is possible to limit the rate at which a single IP (or IPv6/64) can upload new
> or updated keys.

A determined attacker can already simply increment their IID on a v6
capable interface through a /64... so I'm not sure limits/ip are
helpful.

A coordinated botnet of ~200k (not unheard of) ipv4 connected
endpoints could also busily upload to local keyservers 1 key per
second.

-chris


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Valentin Sundermann
In reply to this post by Kiss Gabor (Bitman)
Hi,
> Can we add a proof of work mechanism to make adding a key to the server
> more "costly" ?.
There are some blockchain based approaches on how to distribute keys (or
managing identity) like Blockstack(.org) with their "blockchain id".
Their current model is, that you order a normal name (like domain names)
via a bitcoin/altcoin transaction for a certain price.
I read somewhere that there is support for free namespaces but I don't
know if they use the proof of work concept too.

It's not really related, but I think a keyserver with blockchain id
support which speaks the usual protocol towards the client would be
really great.

Though it don't solves any problems with SKS, I think it's worth a mention.

Best regards,
Valentin

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Christian Felsing-3
Am 25.05.2016 um 18:13 schrieb Valentin Sundermann:
> Hi,
>> Can we add a proof of work mechanism to make adding a key to the server
>> more "costly" ?.


Let client solve a simple integer factorization of a random number given
by server with e.g. 64bit build from two prime numbers. Client has to
find those prime numbers. Until "Can integer factorization be done in
polynomial time?" is answered with "yes" this can be seen as a "hard
problem" so even quite powerful cpus will need a few seconds to solve that.

Christian



_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

smime.p7s (5K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Robert J. Hansen-3
> Let client solve a simple integer factorization of a random number given
> by server with e.g. 64bit build from two prime numbers.

Please sanity-check your ideas first.

Trial division on a 64-bit number requires trying each prime up to
2**32.  There are about 200 million of them.  200 million * 4 bytes per
is a <1GiB database.  You can spread the task over cores -- it's
trivially parallelizable; Amdahl's Law looks at this and starts licking
its lips.

A smartphone can factor a 64-bit composite in ~100 milliseconds.

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Pascal Levasseur-2
In reply to this post by Christian Felsing-3
The administrators of the SKS servers should be able to choose the level
of complexity of the proof of work using a parameter in the SKS server
configuration file.

Using this parameter they could adjust the complexity of the proof of work :

- to the inevitable increase of performance of CPU/GPU,

- to quickly react by increasing complexity if SKS servers are under
"attack".

Pascal

Le 25/05/2016 18:31, Christian Felsing a écrit :

> Am 25.05.2016 um 18:13 schrieb Valentin Sundermann:
>> Hi,
>>> Can we add a proof of work mechanism to make adding a key to the server
>>> more "costly" ?.
>
>
> Let client solve a simple integer factorization of a random number given
> by server with e.g. 64bit build from two prime numbers. Client has to
> find those prime numbers. Until "Can integer factorization be done in
> polynomial time?" is answered with "yes" this can be seen as a "hard
> problem" so even quite powerful cpus will need a few seconds to solve that.
>
> Christian
>
>
>
>
> _______________________________________________
> Sks-devel mailing list
> [hidden email]
> https://lists.nongnu.org/mailman/listinfo/sks-devel
>


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Moritz Wirth
I think that rate limiting new or updated keys may be a good idea. My
keyserver currently recieves about 50-150 keys every hour, limiting this
to something like 300 keys in 10 minutes may help.



Am 26.05.16 um 09:42 schrieb Pascal Levasseur:

> The administrators of the SKS servers should be able to choose the level
> of complexity of the proof of work using a parameter in the SKS server
> configuration file.
>
> Using this parameter they could adjust the complexity of the proof of work :
>
> - to the inevitable increase of performance of CPU/GPU,
>
> - to quickly react by increasing complexity if SKS servers are under
> "attack".
>
> Pascal
>
> Le 25/05/2016 18:31, Christian Felsing a écrit :
>> Am 25.05.2016 um 18:13 schrieb Valentin Sundermann:
>>> Hi,
>>>> Can we add a proof of work mechanism to make adding a key to the server
>>>> more "costly" ?.
>>
>>
>> Let client solve a simple integer factorization of a random number given
>> by server with e.g. 64bit build from two prime numbers. Client has to
>> find those prime numbers. Until "Can integer factorization be done in
>> polynomial time?" is answered with "yes" this can be seen as a "hard
>> problem" so even quite powerful cpus will need a few seconds to solve that.
>>
>> Christian
>>
>>
>>
>>
>> _______________________________________________
>> Sks-devel mailing list
>> [hidden email]
>> https://lists.nongnu.org/mailman/listinfo/sks-devel
>>
>
>
>
>
> _______________________________________________
> Sks-devel mailing list
> [hidden email]
> https://lists.nongnu.org/mailman/listinfo/sks-devel
>

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (846 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Robert J. Hansen-3
In reply to this post by Pascal Levasseur-2
> The administrators of the SKS servers should be able to choose the level
> of complexity of the proof of work using a parameter in the SKS server
> configuration file.

No, they shouldn't.  Think about it.  If you're an attacker looking to
bypass this mechanism, what do you do?  You find the keyserver operator
with the lowest proof-of-work, upload there, and bam, they're propagated
to the high proof-of-work servers.

The proof-of-work required through the system is the *lowest* of all the
keyserver operators.

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Martin Papik

I have a few thoughts, if I may.

If I understand the gist of this discussion you're trying to clean up
bad entries and add a support to delete such entries on a regular basis.
I think this is a dangerous idea, maybe not completely bad, but IMHO it
requires very careful thought. The reason is that it changes the
fundamental security model of the key server system from an append only
system to an editable system. Removal is edit. Who will edit it, when,
how, who will verify it. And why should I trust these allegedly
trustworthy people not to delete my keys by accident, not to mention the
possibility of doing it maliciously. An append only system is simpler,
by design. And it was my understanding that the existing system was
designed the way it was specifically to avoid having to trust anyone
with deletions and the disk space was accepted as a price. Am I wrong in
this? There's also the question of how one can determine if a key is
bogus or valid and how can a set of administrators come to the same
conclusion independently. And will this put the system in the hands of a
few?

Second, I saw a mention of proof of work, while it's a good idea in many
cases, but I have my doubts in this specific case. There are existing
clients out there that know how to publish keys. Adding a proof of work
to the system will disconnect these clients or invalidate the proof of
work system. Doesn't it? Clients may need to be modified, transition
need to be considered, at the very least.

I understand that the system is under load that's considered
unnecessary, maybe even abused. But IMHO changes to the fundamental
properties of the system need to be very seriously considered. Will it
weaken the system's security properties and will the changes be
backwards compatible, these are the questions I bring to the discussion.


Martin

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Pascal Levasseur-2
In reply to this post by Robert J. Hansen-3


Le 26/05/2016 18:51, Robert J. Hansen a écrit :

>> The administrators of the SKS servers should be able to choose the level
>> of complexity of the proof of work using a parameter in the SKS server
>> configuration file.
>
> No, they shouldn't.  Think about it.  If you're an attacker looking to
> bypass this mechanism, what do you do?  You find the keyserver operator
> with the lowest proof-of-work, upload there, and bam, they're propagated
> to the high proof-of-work servers.
>
> The proof-of-work required through the system is the *lowest* of all the
> keyserver operators.
>
Let's have a look at Hashcash as a POW mechanism.

Suppose we add a POW data to the PGP key data transaction request

We can use the number of 0 in the 160-bit SHA-1 hash as the level of
complexity indicator.

The servers who receive a request from an user software to add a key can
easily check the number of zero to find the level of POW and accept or
not the request.

The same mechanism can be used between servers for database reconciliation.

Please feel free to find the weaknesses in this suggestion !!!

Pascal


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Kim Minh Kaplan
Pascal Levasseur wrote:
>
> Please feel free to find the weaknesses in this suggestion !!!

You have no knowledgeable people to implement it.
--
Kim Minh.

_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Andrew Gallagher
In reply to this post by Pascal Levasseur-2
On 27/05/16 12:54, Pascal Levasseur wrote:
>
> Please feel free to find the weaknesses in this suggestion !!!

The fundamental weakness in the proof of work requirement is trying to
apply it in a complex, distributed, synchronising system. The natural
place to require proof-of-work is in the process of (certification)
signature generation, but that's an OpenPGP issue...

A


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (817 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Oh, Jeeez...!

Samir Nassar-2
In reply to this post by Kiss Gabor (Bitman)
On 05/24/2016 06:33 AM, Kiss Gabor (Bitman) wrote:
> Have you remembered I'm continuosly worrying about
> trolls pumping 10-20 millions of dummy keys into key servers?
> It is started...

Is there a technical reason why a keyserver like SKS can't remain
append-only but require that all submitted keys be submitted via
PGP-signed request of the key-owner?

Wouldn't this help mitigate this kind of griefing?

Samir

--
Samir Nassar
web: samirnassar.com
email: [hidden email]
PGP: pgp.samirnassar.com


_______________________________________________
Sks-devel mailing list
[hidden email]
https://lists.nongnu.org/mailman/listinfo/sks-devel

signature.asc (836 bytes) Download Attachment
12