Ygthkb

Found a major flaw in paper from home university – to which I would like to return

What is the reason behind this musical reference to Pinocchio in the Close Encounters main theme?

Coworker is trying to get me to sign his petition to run for office. How to decline politely?

Did the characters in Moving Pictures not know about cameras like Twoflower's?

Minimum Viable Product for RTS game?

Cryptic cross... with words

Exploding Numbers

Now...where was I?

Why don't programs completely uninstall (remove all their files) when I remove them?

How bad is a Computer Science course that doesn't teach Design Patterns?

How do I avoid the "chosen hero" feeling?

Was Opportunity's last message to Earth "My battery is low and it's getting dark"?

Multiple null checks in Java 8

What does "don't have a baby" imply or mean in this sentence?

For the Circle of Spores druid's Halo of Spores feature, is your reaction used regardless of whether the other creature succeeds on the saving throw?

How to know if I am a 'Real Developer'

What does @ mean in a hostname in DNS configuration?

When distributing a Linux kernel driver as source code, what's the difference between Proprietary and GPL license?

What is an explicit bijection in combinatorics?

Minimum energy path of a potential energy surface

Coworker asking me to not bring cakes due to self control issue. What should I do?

Is there a way to pause a running process on Linux systems and resume later?

Generate PGP keys very very fast

Identical projects by students at two different colleges: still plagiarism?

Generate PGP keys very very fast

Proper way to generate symmetric keysWhy must we generate the signature before any compression being done at PGP?Initializing PGP keys by one sideHow to generate fingerprint for PGP public keyAre the metadata encrypted by PGP?What is “Fast Prime”?Key expansion for cryptographic keysAlgorithm to generate ECDSA keys with random number generatorWeaknesses in vanity PGP keysHow to generate a distributed private key?

1

$begingroup$

Is there a way to generate thousands of PGP keys at a very very fast rate?

I am generating thousands of 3072-bit PGP keys looking like part of a personal research project. Obviously, this is a very slow, CPU intensive activity. I have turned off strong randomization with the --debug-quick-random, am generating them using --batch and maxed out all of my personal CPUs. But this is still not fast enough.

Is there a way to generate perhaps thousands of keys very rapidly? My goal is to get a 16-bit hash collision on the KeyID. I know this is entirely impractical for real security, this is mostly for research purposes. I have not reviewed the GnuPG code, but I am trying to avoid writing any code just yet.

Thanks!

pgp key-generation

share|improve this question

edited 4 hours ago

kelalaka

7,96822350

asked 5 hours ago

Farhan YusufzaiFarhan Yusufzai

61

New contributor

Farhan Yusufzai is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Do you require to have RSA keys? ECC keys can be generated much faster, and they're supported in the more recent versions of GPG.
  $endgroup$
  – Ruben De Smet
  8 mins ago
  

  
  
  
  

add a comment | 

1

$begingroup$

Is there a way to generate thousands of PGP keys at a very very fast rate?

I am generating thousands of 3072-bit PGP keys looking like part of a personal research project. Obviously, this is a very slow, CPU intensive activity. I have turned off strong randomization with the --debug-quick-random, am generating them using --batch and maxed out all of my personal CPUs. But this is still not fast enough.

Is there a way to generate perhaps thousands of keys very rapidly? My goal is to get a 16-bit hash collision on the KeyID. I know this is entirely impractical for real security, this is mostly for research purposes. I have not reviewed the GnuPG code, but I am trying to avoid writing any code just yet.

Thanks!

pgp key-generation

share|improve this question

edited 4 hours ago

kelalaka

7,96822350

asked 5 hours ago

Farhan YusufzaiFarhan Yusufzai

61

New contributor

Farhan Yusufzai is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Do you require to have RSA keys? ECC keys can be generated much faster, and they're supported in the more recent versions of GPG.
  $endgroup$
  – Ruben De Smet
  8 mins ago
  

  
  
  
  

add a comment | 

$begingroup$

Is there a way to generate thousands of PGP keys at a very very fast rate?

I am generating thousands of 3072-bit PGP keys looking like part of a personal research project. Obviously, this is a very slow, CPU intensive activity. I have turned off strong randomization with the --debug-quick-random, am generating them using --batch and maxed out all of my personal CPUs. But this is still not fast enough.

Is there a way to generate perhaps thousands of keys very rapidly? My goal is to get a 16-bit hash collision on the KeyID. I know this is entirely impractical for real security, this is mostly for research purposes. I have not reviewed the GnuPG code, but I am trying to avoid writing any code just yet.

Thanks!

pgp key-generation

share|improve this question

edited 4 hours ago

kelalaka

7,96822350

asked 5 hours ago

Farhan YusufzaiFarhan Yusufzai

61

New contributor

Farhan Yusufzai is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|improve this question

edited 4 hours ago

kelalaka

7,96822350

asked 5 hours ago

Farhan YusufzaiFarhan Yusufzai

61

New contributor

Farhan Yusufzai is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|improve this question

edited 4 hours ago

kelalaka

7,96822350

asked 5 hours ago

Farhan YusufzaiFarhan Yusufzai

61

New contributor

Farhan Yusufzai is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

edited 4 hours ago

kelalaka

7,96822350

edited 4 hours ago

kelalaka

7,96822350

asked 5 hours ago

Farhan YusufzaiFarhan Yusufzai

61

New contributor

Farhan Yusufzai is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked 5 hours ago

Farhan YusufzaiFarhan Yusufzai

61

2 Answers
2

active

oldest

votes

3

$begingroup$

To generate keys faster than you are doing right now probably requires to add a faster source of random numbers to your system. You could look at the extensions available in your CPU and checking if they are enabled or not on your system.

---

If you are only interested in looking for collision on key ID, you'd probably proceed differently.

fingerprint = hash(public_key) public_key = timestamp +
public_key_data

Therefore:

fingerprint = hash(timestamp + public_key_data)

There's a script that manipulate only the timestamp looking for a collision.
https://github.com/micahflee/trollwot

share|improve this answer

answered 3 hours ago

ddddavideeddddavidee

2,68611429

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  +1 for the idea of changing only the timestamp!
  $endgroup$
  – fgrieu
  2 hours ago
  

  
  
  
  

add a comment | 

0

$begingroup$

Yes.

As rightly pointed in the first answer, we can make keys with identical public-key parameters but a different timestamp, which makes computing a fingerprint very fast. That seems by far the fastest/best to create collisions.

We create $kge2$ keys (say 16), compute fingerprints with varying timestamps, find a collision, and check that they are not with the same key (which as probability $1/k$). We can use the techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999 to make that search with only little memory, and several independent devices (or independent data streams in SIMD/GPU computing).

In retrospect, PGP/GPG key fingerprint should have used a purposely slow hash rather than plain SHA-1. At least, something like PBKDF2; nowadays we'd use Argon2(id?), or Balloon Hashing.

_{I previously came up with speedup techniques, which are out not useful for the task at hand. They RIP there.}

share|improve this answer

edited 2 hours ago

answered 3 hours ago

fgrieufgrieu

80.3k7171338

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I liked the "other speedup techniques". I'm glad they're still in the revision history.
  $endgroup$
  – ddddavidee
  2 hours ago
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

Farhan Yusufzai is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f67529%2fgenerate-pgp-keys-very-very-fast%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

To generate keys faster than you are doing right now probably requires to add a faster source of random numbers to your system. You could look at the extensions available in your CPU and checking if they are enabled or not on your system.

---

If you are only interested in looking for collision on key ID, you'd probably proceed differently.

fingerprint = hash(public_key) public_key = timestamp +
public_key_data

Therefore:

fingerprint = hash(timestamp + public_key_data)

There's a script that manipulate only the timestamp looking for a collision.
https://github.com/micahflee/trollwot

share|improve this answer

answered 3 hours ago

ddddavideeddddavidee

2,68611429

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  +1 for the idea of changing only the timestamp!
  $endgroup$
  – fgrieu
  2 hours ago
  

  
  
  
  

add a comment | 

3

$begingroup$

To generate keys faster than you are doing right now probably requires to add a faster source of random numbers to your system. You could look at the extensions available in your CPU and checking if they are enabled or not on your system.

---

If you are only interested in looking for collision on key ID, you'd probably proceed differently.

fingerprint = hash(public_key) public_key = timestamp +
public_key_data

Therefore:

fingerprint = hash(timestamp + public_key_data)

There's a script that manipulate only the timestamp looking for a collision.
https://github.com/micahflee/trollwot

share|improve this answer

answered 3 hours ago

ddddavideeddddavidee

2,68611429

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  +1 for the idea of changing only the timestamp!
  $endgroup$
  – fgrieu
  2 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

To generate keys faster than you are doing right now probably requires to add a faster source of random numbers to your system. You could look at the extensions available in your CPU and checking if they are enabled or not on your system.

---

If you are only interested in looking for collision on key ID, you'd probably proceed differently.

fingerprint = hash(public_key) public_key = timestamp +
public_key_data

Therefore:

fingerprint = hash(timestamp + public_key_data)

There's a script that manipulate only the timestamp looking for a collision.
https://github.com/micahflee/trollwot

share|improve this answer

answered 3 hours ago

ddddavideeddddavidee

2,68611429

$endgroup$

share|improve this answer

answered 3 hours ago

ddddavideeddddavidee

2,68611429

answered 3 hours ago

ddddavideeddddavidee

2,68611429

answered 3 hours ago

ddddavideeddddavidee

2,68611429

0

$begingroup$

Yes.

As rightly pointed in the first answer, we can make keys with identical public-key parameters but a different timestamp, which makes computing a fingerprint very fast. That seems by far the fastest/best to create collisions.

We create $kge2$ keys (say 16), compute fingerprints with varying timestamps, find a collision, and check that they are not with the same key (which as probability $1/k$). We can use the techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999 to make that search with only little memory, and several independent devices (or independent data streams in SIMD/GPU computing).

In retrospect, PGP/GPG key fingerprint should have used a purposely slow hash rather than plain SHA-1. At least, something like PBKDF2; nowadays we'd use Argon2(id?), or Balloon Hashing.

_{I previously came up with speedup techniques, which are out not useful for the task at hand. They RIP there.}

share|improve this answer

edited 2 hours ago

answered 3 hours ago

fgrieufgrieu

80.3k7171338

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I liked the "other speedup techniques". I'm glad they're still in the revision history.
  $endgroup$
  – ddddavidee
  2 hours ago
  

  
  
  
  

add a comment | 

0

$begingroup$

Yes.

As rightly pointed in the first answer, we can make keys with identical public-key parameters but a different timestamp, which makes computing a fingerprint very fast. That seems by far the fastest/best to create collisions.

We create $kge2$ keys (say 16), compute fingerprints with varying timestamps, find a collision, and check that they are not with the same key (which as probability $1/k$). We can use the techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999 to make that search with only little memory, and several independent devices (or independent data streams in SIMD/GPU computing).

In retrospect, PGP/GPG key fingerprint should have used a purposely slow hash rather than plain SHA-1. At least, something like PBKDF2; nowadays we'd use Argon2(id?), or Balloon Hashing.

_{I previously came up with speedup techniques, which are out not useful for the task at hand. They RIP there.}

share|improve this answer

edited 2 hours ago

answered 3 hours ago

fgrieufgrieu

80.3k7171338

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I liked the "other speedup techniques". I'm glad they're still in the revision history.
  $endgroup$
  – ddddavidee
  2 hours ago
  

  
  
  
  

add a comment | 

$begingroup$

Yes.

As rightly pointed in the first answer, we can make keys with identical public-key parameters but a different timestamp, which makes computing a fingerprint very fast. That seems by far the fastest/best to create collisions.

We create $kge2$ keys (say 16), compute fingerprints with varying timestamps, find a collision, and check that they are not with the same key (which as probability $1/k$). We can use the techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999 to make that search with only little memory, and several independent devices (or independent data streams in SIMD/GPU computing).

In retrospect, PGP/GPG key fingerprint should have used a purposely slow hash rather than plain SHA-1. At least, something like PBKDF2; nowadays we'd use Argon2(id?), or Balloon Hashing.

_{I previously came up with speedup techniques, which are out not useful for the task at hand. They RIP there.}

share|improve this answer

edited 2 hours ago

answered 3 hours ago

fgrieufgrieu

80.3k7171338

$endgroup$

share|improve this answer

edited 2 hours ago

answered 3 hours ago

fgrieufgrieu

80.3k7171338

answered 3 hours ago

fgrieufgrieu

80.3k7171338

answered 3 hours ago

fgrieufgrieu

80.3k7171338