Complexities on faking one signature

classic Classic list List threaded Threaded
4 messages Options
iry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Complexities on faking one signature

iry
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

Hello everyone!

When an adversary attempts to create someone's GPG signature of a
certain message, there are at least two ways to do so:
1. Computing the private key from the public key of the target and
then using the private key to sign the message;
2. Enumerating the possible signature of that certain message and
using the target's public key to verify if one of the signatures is
correct.

If other conditions are same and the adversary only needs to get the
target's signature of one certain message, will the second approach
easier than the first approach in terms of computing complexity?

I'm really looking forward to the answer and/or further discussion!
Thank you!

Best,
iry
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJY4HjiAAoJEKFLTbxtzdU8d4QP/2UvpLxY3E2lhN3YVwmQnWMO
O/X9svCSsrFLZZU6jskQn0zTTDr05TzYI3xKHOrAocllULMzTHF8Q1X47pUGtdI/
Y2Oa32A387e8bjaSA+iLBuhyfwkRXkNvKy8iwHaG6353i/7hS8EHGugsZYNeXKIv
P7wHfaJFZ/7vj4BD4vQZAiLIU0W3jMslHNvNvp1jHSxyiHnM9o+bhdJd7WsqCD6A
hAaUP1OAffKSjuM85QpmnsOW29SkkCMVDlyrNtDS58eBup2fxv3YCwzBdH53vnhY
tNA5g/KclndmGD5IagacN90hB6cX/LTl55kWDgJdKRqKlMAkhnY4zllWdtM9dcp9
+3NYbWQptxgnfCqVeMLoUew0ioORjDjLulFRHM+X5iNdyanNgCA5H/4wOu4jlb6f
dRK8xnzJ4wzVTQONDHDd9B5xQ1cKy1nqi+aeGpmkMJqFmY87ijd32rseWkTe5uKk
TYRN8je9RQgLmJ7AYlngTEYw8frsMvprX/zLY88pYe99r2Ggc559yxu9zemqcwpv
adWUUbc9ztJybDh4Py7EWSGR/6o2OUAoMlF80petRbDKJbSi/zE/C5HrczKHJkGS
cgnW9CQxbJxkePnB6GbGo6tA5TYhcBzJ+8NaCZCFMonkg4ihPIqTLoIIZe/OGYZ4
GK65uMtyc4w8gRjC6sKl
=OYVh
-----END PGP SIGNATURE-----

_______________________________________________
Gnupg-users mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-users

0x6DCDD53C.asc (3K) Download Attachment
0x6DCDD53C.asc.sig (744 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Complexities on faking one signature

Robert J. Hansen-3
> 1. Computing the private key from the public key of the target and
> then using the private key to sign the message;

The difficulty of this is dependent on the length of the asymmetric key.
 NIST's guidance is that cracking a 1024-bit key is about 2**80 work, a
2048-bit key is about 2**112 work, and a 3072-bit key is about 2**128 work.

> 2. Enumerating the possible signature of that certain message and
> using the target's public key to verify if one of the signatures is
> correct.

I'm not sure what you mean here; that's not how signatures work.
Signatures work by computing a digest over data and encrypting that with
the private key.  Since you lack the private key, you can't generate
signatures.

What you could do instead is look at an earlier message your target
signed, get the digest of that, and generate new messages until you
created one with an identical digest.  The difficulty of this will
depend on your target's signature:

DSA-1024: 2**159 work
DSA-2048: 2**223 work
DSA-3072: 2**255 work
RSA: varies by user prefs, but unlikely to be under 2**159

You'll notice the work to break the hash is almost exactly the square of
the work to break the key.  This is not an accident.  :)

_______________________________________________
Gnupg-users mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Complexities on faking one signature

Wouter Verhelst
On Sun, Apr 02, 2017 at 07:12:38PM -0400, Robert J. Hansen wrote:
> > 2. Enumerating the possible signature of that certain message and
> > using the target's public key to verify if one of the signatures is
> > correct.
>
> I'm not sure what you mean here; that's not how signatures work.
> Signatures work by computing a digest over data and encrypting that with
> the private key.  Since you lack the private key, you can't generate
> signatures.

No, but you can generate random numbers and verify whether they happen
to be a valid signature.

I believe the OP is asking whether it'd be easier to brute-force a
signature than it is to brute-force a private key.

With RSA, the signature is exactly the same length as the (public) key.
Therefore, naively, one could assume that the complexity would be
approximately the same too.

In practice, however, the work required to brute-force a signature is
probably worse than that to brute-force a private key, because the
public key must be the product of the private key's two prime numbers
(which limits their values to things that can reasonably be the public
key's divisors, and you can preselect for that), whereas a signature is
a modulus and can therefore be pretty much anything.

--
< ron> I mean, the main *practical* problem with C++, is there's like a dozen
       people in the world who think they really understand all of its rules,
       and pretty much all of them are just lying to themselves too.
 -- #debian-devel, OFTC, 2016-02-12

_______________________________________________
Gnupg-users mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Complexities on faking one signature

Robert J. Hansen-3
> I believe the OP is asking whether it'd be easier to brute-force a
> signature than it is to brute-force a private key.

Unimaginably harder to brute-force a sig.

Since RSA is deterministic (at least, naïve RSA is), a sig is done on a
digest (of let's say size 256 bits) and there are 2**256 different valid
outputs.  But the signature length itself is thousands of bits, for
2**thousands of possibilities.  So the per-attempt likelihood of finding
one of the 2**256 valid signatures out of a signature of 2**thousands of
bits is likelihood is 2**(256 - thousands).

2**-2000 is so close to zero as makes no difference whatsoever.

_______________________________________________
Gnupg-users mailing list
[hidden email]
http://lists.gnupg.org/mailman/listinfo/gnupg-users
Loading...