How to crack Netrek RSA binary verification system
Bob Dang
Select two primes p and q
Calculate n = p q
Calculate f(n) = (p-1)(q-1)
Select e such that 1 < e < f(n) and gcd(f(n),e) = 1
Calculate d = e^-1 mod f(n)
Public key KU = {e,n}
Private key KR = {d,n}
Example
Select two primes p=7 and q=17
Calculate n = p q = 119
Calculate f(n) = (p-1)(q-1) = 96
Select e such that 1 < e < f(n) and gcd(f(n),e) = 1, e.g., e = 5
Calculate d = e^-1 mod f(n), e.g., d = 77
Public key KU = {e,n} = {5,119}
Private key KR = {d,n} = {77,119}
Cracking RSA
Factor n, which is public, yielding p and q
Calculate f(n) = (p-1)(q-1)
Calculate d = e^-1 mod f(n) (e is public)
Private key KR = {d,n}
Note: you can check your calculation of d because d e = 1 mod f(n)
Cracking RSA (Example)
Factor 119, which is public, yielding 7 and 17
Calculate f(119) = (7-1)(17-1) = 96
Calculate 5^-1 = 77 mod 96
Private key KR = {77,119}
Plaintext M = 19
Ciphertext C = Me mod n = 195 mod 119 = 66
Plaintext M = Cd mod n = 6677 mod 119 = 19
-------------------------------------------
Netrek RSA Specifics:
Go to http://65.193.17.240:3530/ and select a key. Try:
key.brmh2.sun4:ct=BRM-Hadley:cr=had...@uci.edu:\
:cd=September 1994:ar=Sun4 / SunOS 4.1.2:cl=inl,standard2:\
:cm=At cad.ics.uci.edu-/pub/netrek:\
:gk=636a5977da5ce59948885d1003e983deabf405ed0cb952a5b42930523909f901:\
:pk=0dfc24f1d19398586dafa37e985163290eb01f139c03f90affc5d458a7f6b800:
Convert gk and pk to integers. Note gk and pk are little endian, so
they must be reversed and converted. I used java:
//be2i.java : converts gk and pk to plain integers
//
import java.math.BigInteger;
public class be2i {
static BigInteger GLOBAL_KEY = new
BigInteger(swapEndian("636a5977da5ce59948885d1003e983deabf405ed0cb952a5b42930523909f901"),
16);
static BigInteger PUBLIC_KEY = new
BigInteger(swapEndian("0dfc24f1d19398586dafa37e985163290eb01f139c03f90affc5d458a7f6b800"),
16);
static String swapEndian(String s)
{
char c[] = s.toCharArray();
StringBuffer buffer = new StringBuffer(c.length);
for(int i = c.length; (i -= 2) >= 0;)
{
buffer.append(c[i]);
buffer.append(c[i + 1]);
}
return buffer.toString();
}
public static void main(String args[]) {
System.out.println(GLOBAL_KEY.toString(10));
System.out.println(PUBLIC_KEY.toString(10));
}
}
E:\be2i>javac -d . be2i.java
E:\be2i>java be2i
892321428802586219001502719778378451271677716961403333724586529659410803299
326802201186638185587649392739171025726846542356328056267675213531974007821
Note:
gk=892321428802586219001502719778378451271677716961403333724586529659410803299
pk=326802201186638185587649392739171025726846542356328056267675213531974007821
Factor gk. Download PARI/GP http://pari.math.u-bordeaux.fr/ Install
it, then run it:
Reading GPRC: /cygdrive/c/Program Files/PARI/.gprc ...Done.
GP/PARI CALCULATOR Version 2.2.8 (development CHANGES-1.887)
i686 running cygwin (ix86 kernel) 32-bit version
compiled: Jan 13 2004, gcc-3.3.1 (cygming special)
(readline v4.3 enabled, extended help available)
Copyright (C) 2003 The PARI Group
PARI/GP is free software, covered by the GNU General Public License,
and
comes WITHOUT ANY WARRANTY WHATSOEVER.
Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.
realprecision = 28 significant digits
seriesprecision = 16 significant terms
format = g0.28
parisize = 4000000, primelimit = 500000
(19:29) gp > factorint(892321428802586219001502719778378451271677716961403333724586529659410803299)
*** Warning: MPQS: the factorization of this number will take
several hours.
%1 =
[6158427920916659824908651606478252183 1]
[144894352951973396937037531927458847253 1]
(21:29) gp >
Calculate d = e^-1 mod f(n) (e is public)
Download res-rsa-2.9.2
ftp://ftp.netrek.org/pub/netrek/rsa/res-rsa-2.9.2.tar.gz
Modify mkkey.c as follows:
/* mpz_set_ui(x, 0); */
/* mpz_set_ui(y, 0); */
/* mpz_set_ui(global, 0); */
mpz_set_str(x,"6158427920916659824908651606478252183", 0);
mpz_set_str(y, "144894352951973396937037531927458847253", 0);
mpz_set_str
(global, "892321428802586219001502719778378451271677716961403333724586529659410803299",
0);
mpz_set_str
(private, "326802201186638185587649392739171025726846542356328056267675213531974007821",
0);
/* mpz_set_ui(public, 0); */
mpz_set_ui(public, 0);
mpz_set_ui(xyminus1, 0);
/* here we find x and y, two large primes */
rand_raw(temp, HALF);
temp[0] |= 1; /* force odd */
/* raw_to_num(x, temp); */
while (!is_prime(x))
mpz_add(x, x, two);
check_positive(x);
assert(is_prime(x));
rand_raw(temp, HALF);
temp[0] |= 1; /* force odd */
/* raw_to_num(y, temp); */
while (!is_prime(y))
mpz_add(y, y, two);
check_positive(y);
assert(is_prime(y));
/* the private key is a large prime (it should be the larger than
* x & y) */
rand_raw(temp, HALF + 1);
temp[0] |= 1; /* force odd */
//raw_to_num(private, temp);
// while (!is_prime(private))
// mpz_add(private, private, two);
check_positive(private);
//assert(is_prime(private));
Note rest of mkkeys.c is unchanged.
cherry:/home/bd/netrek/mkkey/res-rsa-2.9.2$ diff mkkey.c mkkey-mine.c
1103,1106c1119,1129
< mpz_set_ui(x, 0);
< mpz_set_ui(y, 0);
< mpz_set_ui(global, 0);
< mpz_set_ui(private, 0);
---
> /* mpz_set_ui(x, 0); */
> /* mpz_set_ui(y, 0); */
> /* mpz_set_ui(global, 0); */
>
> mpz_set_str(x,"6158427920916659824908651606478252183", 0);
> mpz_set_str(y, "144894352951973396937037531927458847253", 0);
> mpz_set_str
> (global, "892321428802586219001502719778378451271677716961403333724586529659410803299", 0);
> mpz_set_str
> (private, "326802201186638185587649392739171025726846542356328056267675213531974007821", 0);
> /* mpz_set_ui(public, 0); */
1114c1137
< raw_to_num(x, temp);
---
> /* raw_to_num(x, temp); */
1124c1147
< raw_to_num(y, temp);
---
> /* raw_to_num(y, temp); */
1137c1160
< raw_to_num(private, temp);
---
> //raw_to_num(private, temp);
1139,1140c1162,1163
< while (!is_prime(private))
< mpz_add(private, private, two);
---
> // while (!is_prime(private))
> // mpz_add(private, private, two);
1143c1166
< assert(is_prime(private));
---
> //assert(is_prime(private));
cherry:/home/bd/netrek/mkkey/res-rsa-2.9.2$ make
gcc -O2 -c mkkey.c
gcc -O2 -o mkkey mkkey.o -lgmp
cherry:/home/bd/netrek/mkkey/res-rsa-2.9.2$ ./mkkey foo foo foo foo
foo
mkkey version [RES-RSA 2.9.2: Mar. 13, 2000][GMP]
Source basename: "rsa_box"
Number of shells: 3
Number of steps between swaps: 2
Number of files: 5
Ratio of computation in files to main file: 0.8
Making new key, hold on....
Testing key .................................................. key
seems OK
Writing...
240 bits left, 5 files left, 37 bits in rsa_box_0.c
202 bits left, 4 files left, 7 bits in main file
194 bits left, 4 files left, 42 bits in rsa_box_1.c
151 bits left, 3 files left, 11 bits in main file
139 bits left, 3 files left, 29 bits in rsa_box_2.c
109 bits left, 2 files left, 10 bits in main file
98 bits left, 2 files left, 32 bits in rsa_box_3.c
65 bits left, 1 files left, 13 bits in main file
51 bits left, 1 files left, 39 bits in rsa_box_4.c
cherry:/home/bd/netrek/mkkey/res-rsa-2.9.2$ cat foo.secret
foo:ct=foo:cr=foo:\
:cd=September 2004:ar=foo:\
:cm=foo:\
:gk=636a5977da5ce59948885d1003e983deabf405ed0cb952a5b42930523909f901:\
:pk=057505d6c5b0b5ccd0f7819a7670da469e000000000000000000000000000000:\
:sk=0dfc24f1d19398586dafa37e985163290eb01f139c03f90affc5d458a7f6b800:
Note pk and sk are reversed. Edit foo.secret to correct the order to:
foo:ct=foo:cr=foo:\
:cd=September 2004:ar=foo:\
:cm=foo:\
:gk=636a5977da5ce59948885d1003e983deabf405ed0cb952a5b42930523909f901:\
:pk=0dfc24f1d19398586dafa37e985163290eb01f139c03f90affc5d458a7f6b800:\
:sk=057505d6c5b0b5ccd0f7819a7670da469e000000000000000000000000000000:
Rerun mkkey with the edited secret key file:
cherry:/home/bd/netrek/mkkey/res-rsa-2.9.2$ ./mkkey -k foo.secret
mkkey version [RES-RSA 2.9.2: Mar. 13, 2000][GMP]
Source basename: "rsa_box"
Number of shells: 3
Number of steps between swaps: 2
Number of files: 5
Ratio of computation in files to main file: 0.8
Reading key from keycap file "foo.secret"...
Testing key .................................................. key
seems OK
Writing...
128 bits left, 5 files left, 19 bits in rsa_box_0.c
108 bits left, 4 files left, 6 bits in main file
101 bits left, 4 files left, 20 bits in rsa_box_1.c
80 bits left, 3 files left, 5 bits in main file
74 bits left, 3 files left, 15 bits in rsa_box_2.c
58 bits left, 2 files left, 6 bits in main file
51 bits left, 2 files left, 21 bits in rsa_box_3.c
29 bits left, 1 files left, 5 bits in main file
23 bits left, 1 files left, 14 bits in rsa_box_4.c
cherry:/home/bd/netrek/mkkey/res-rsa-2.9.2$ ls -aFl rsa_box_?.c
-rw-r--r-- 1 bd bd 3856 Sep 19 20:02 rsa_box_0.c
-rw-r--r-- 1 bd bd 4093 Sep 19 20:02 rsa_box_1.c
-rw-r--r-- 1 bd bd 3222 Sep 19 20:02 rsa_box_2.c
-rw-r--r-- 1 bd bd 4368 Sep 19 20:02 rsa_box_3.c
-rw-r--r-- 1 bd bd 3130 Sep 19 20:02 rsa_box_4.c
cherry:/home/bd/netrek/mkkey/res-rsa-2.9.2$
Copy rsa_box_?.c files into your own custom client source directory,
compile, and login to any public netrek server, including INL server
of your choice.
-bd
Jonathan Ellis
-Jonathan
Bob Dang wrote:
> The RSA Algorithm ...
Donald Tsang
>Cracking RSA
>
>Factor n, which is public, yielding p and q
Umm, duh? The strength of RSA has always been in the difficulty of
factoring. It's (probably) NP, which means that all of the known
algorithms that accomplish the task take time exponential on the
number of bits in n.
It was only a matter of time before computers got fast enough to do
it in a reasonable amount of time (Moore's Law, which gives a rough
estimate of a doubling of processing power every 18 months, means something
along the lines of "you have to add a bit to the key every 18 months".
It's not as if we haven't had man-in-the-middle attacks, stealing of the
secret keys through runtime debuggers, etc...
If you want to worry about this stuff, figure out how long your
bank card PIN should be. Or look at the (proposed?) laws that would
make an electronic signature as legal as your John Hancock (or equivalent
non-USAian person with famous signature).
The Netrek RSA authentication code has never been anything more than a
way to discourage casual client-hackers from trying to cheat.
Donald Tsang
Stas Pirogov
wrote:
>The RSA Algorithm
>
[snip]
>Copy rsa_box_?.c files into your own custom client source directory,
>compile, and login to any public netrek server, including INL server
>of your choice.
>-bd
Well, the whole process you described here is easy, but still requires
some devotion from the person who tries to get rsa_box*.c files
I personally don't see why this information is published on rgn. It
can only encourage somebody who didn't 'know how' to try. The fact
that netrek RSA is vulnerable to multiple types of breaking is well
known for some time already.
Stas
Zachary Uram
>
> I personally don't see why this information is published on rgn. It
> can only encourage somebody who didn't 'know how' to try. The fact
> that netrek RSA is vulnerable to multiple types of breaking is well
> known for some time already.
Hi Stas,
So you favor the Security Through Obscurity model? ;)
I think it's good to discuss these design weaknesses.
Even using RSA can be criticized as a bad security choice since the RSA
algorithm is public knowledge now. What could we use besides RSA?
Zach
Zachary Uram
> The RSA Algorithm
>
[snip]
Interesting. Is there anyway a server god could detect that one was using
a non-blessed client with a bogus RSA key?
Zach
Sven Neuhaus
is that the flaw?
-Sven
Donald Tsang
>So the keys that are built into the 1994 client are too short,
>is that the flaw?
Umm, sure.
Assuming Moore's Law (processing power doubles every 18 months),
you'd need to add something on the order of seven bits to the length
of the key.
Of course, if you're going to add a few bits, why not just double the
keylength? (answer: there are other security concerns that make this
weakness moot)
Donald
Zachary Uram
>
> Assuming Moore's Law (processing power doubles every 18 months),
> you'd need to add something on the order of seven bits to the length
> of the key.
Hi Donald,
Sometimes it doubles in less than 18 months right?
> Of course, if you're going to add a few bits, why not just double the
> keylength? (answer: there are other security concerns that make this
> weakness moot)
Oh? So what is the use of those long military-grade keys? In your view
does RSA need replacing in netrek and if so what would you use
instead?
Zach
Donald Tsang
>ts...@soda.csua.berkeley.edu (Donald Tsang) wrote:
>> Assuming Moore's Law (processing power doubles every 18 months),
>> you'd need to add something on the order of seven bits to the length
>> of the key.
>
And sometimes it takes longer. Moore's Law has been a fair approximation.
>> Of course, if you're going to add a few bits, why not just double the
>> keylength? (answer: there are other security concerns that make this
>> weakness moot)
>
>Oh? So what is the use of those long military-grade keys? In your view
>does RSA need replacing in netrek and if so what would you use
>instead?
What I meant was, Netrek has enough inherently-insecure aspects
about it that spending a lot of time improving the RSA module is
probably silly. It's been demonstrated in the past that extracting
secret keys from binaries isn't particularly difficult; the things
that prevent lots of people from breaking keys, writing borgs, and
inserting the keys into the borgs include:
(a) not very many people playing Netrek
(b) not very many people having the programming knowledge to do it
(c) not very many people having the time to write borgs
(d) very few people having the antisocial traits required to play a
borg seriously on a non-borg server, and to not care when people
complained.
Donald
Zachary Uram
>
> And sometimes it takes longer. Moore's Law has been a fair approximation.
Ok.
> What I meant was, Netrek has enough inherently-insecure aspects
> about it that spending a lot of time improving the RSA module is
> probably silly. It's been demonstrated in the past that extracting
> secret keys from binaries isn't particularly difficult; the things
> that prevent lots of people from breaking keys, writing borgs, and
> inserting the keys into the borgs include:
Ah, gotcha.
> (a) not very many people playing Netrek
> (b) not very many people having the programming knowledge to do it
> (c) not very many people having the time to write borgs
> (d) very few people having the antisocial traits required to play a
> borg seriously on a non-borg server, and to not care when people
> complained.
So you think we should just leave the RSA mechanism in place as it is?
Zach
Zachary Uram
>
> And sometimes it takes longer. Moore's Law has been a fair approximation.
Ok.
> What I meant was, Netrek has enough inherently-insecure aspects
> about it that spending a lot of time improving the RSA module is
> probably silly. It's been demonstrated in the past that extracting
> secret keys from binaries isn't particularly difficult; the things
> that prevent lots of people from breaking keys, writing borgs, and
> inserting the keys into the borgs include:
Ah, gotcha.
> (a) not very many people playing Netrek
> (b) not very many people having the programming knowledge to do it
> (c) not very many people having the time to write borgs
> (d) very few people having the antisocial traits required to play a
> borg seriously on a non-borg server, and to not care when people
> complained.
So you think we should just leave the RSA mechanism in place as it is?
Zach