Formats ssh and ssh-ng

[Frank Dittrich]

I think ssh and/or ssh-ng formats need at least some documentation, but
preferably even some code changes.


To understand the differences between ssh and ssh-ng formats, I did

https://github.com/search?p=6&q=path%3A.ssh%2Fid_rsa

(Here is where I got the idea: http://blog.fefe.de/?ts=affff7e4)

Then I picked the first file:

https://raw.github.com/shennjia/think/250386366e8dadc7591c1e1f3475fb3374008783/.ssh/id_rsa


Then I did:

$ ./ssh2john id_rsa > ssh-test
and
$ ./sshng2john.py id_rsa > sshng-test

(BTW: I had to install python-crypto on Fedora 18 to make the script work.)

$ ./john ssh-test --incremental
Loaded 1 password hash (SSH RSA/DSA [32/64])
guesses: 0 time: 0:00:00:13 0.00% c/s: 7871 trying: suppichi
guesses: 0 time: 0:00:00:29 0.00% c/s: 8101 trying: baby47
Session aborted

$ ./john sshng-test --incremental
Loaded 1 password hash (ssh-ng SSH RSA / DSA [32/64])
guesses: 0 time: 0:00:00:14 0.00% c/s: 105098 trying: jc6475
guesses: 0 time: 0:00:00:27 0.00% c/s: 108047 trying: ccsdbn
Session aborted

Apparently, both formats are able to crack the same input file after
converting it using the right tool.
But ssh-ng is much faster.


Why does ssh-ng have the "False positives possible" flag set?
If ssh can avoid false positives, ssh-ng should be able to avoid false
positives as well, no?


This:
$ ls -l ssh*test
-rw-rw-r--. 1 fd fd 2425 Jan 24 15:51 sshng-test
-rw-rw-r--. 1 fd fd 3505 Jan 24 15:51 ssh-test
doesn't look like ssh2john is extracting less information from the
keyfile than sshng2john is.
So, shouldn't ssh-ng be able to "understand" and convert $ssh2$ hashes?
What about ssh understanding the $sshng$ hashes?


Why do we even need two different tags?
Why different format names?
Can't ssh-ng report "SSH RSA / DSA" instead of "ssh-ng SSH RSA / DSA"?
This would allow to pick the fastest of several benchmarks for
performance comparison in relbench.
(Of course, the format name should only be changed if both formats
understand the same canonical hash representation and if ssh-ng doesn't
produce false positives.)

What am I missing here?


Frank

[Dhiru Kholia]

On Thu, Jan 24, 2013 at 8:50 PM, Frank Dittrich

Post by Frank Dittrich
I think ssh and/or ssh-ng formats need at least some documentation, but
preferably even some code changes.

Good point. I can quickly write a "README.ssh" file explaining the
usage of and the difference between these two formats.

Post by Frank Dittrich
$ ./sshng2john.py id_rsa > sshng-test
(BTW: I had to install python-crypto on Fedora 18 to make the script work.)

Can you please test the following patch to see if it makes things better?

diff --git a/run/sshng2john.py b/run/sshng2john.py
index 12a6f60..b08a85e 100755
--- a/run/sshng2john.py
+++ b/run/sshng2john.py
@@ -31,10 +31,16 @@ from hashlib import md5 as MD5

limited = False

+
+class Object(object):
+ pass
+
try:
- from Crypto.Cipher import DES3, AES
+ from Crypto.Cipher import DES3, AES1
except ImportError:
print >> sys.stderr, "PyCrypto is missing in your Python
installation, %s is operating is limited features mode!" % sys.argv[0]
+ AES = Object()
+ AES.MODE_CBC = ""
limited = True


@@ -639,7 +645,8 @@ class PKey (object):

if 'proc-type' not in headers:
# unencryped: done
- return data
+ print >> sys.stderr, "%s has no password!" % f.name
+ return None
# encrypted keyfile: will need a password
if headers['proc-type'] != '4,ENCRYPTED':
raise SSHException('Unknown private key structure "%s"' %
headers['proc-type'])
@@ -674,7 +681,7 @@ class PKey (object):
return ddata
except ValueError: # incorrect password
return data
- return None
+ return self.hash # dummy value


def chunks(l, n):
@@ -717,6 +724,8 @@ class RSADSSKey (PKey):
def _from_private_key_file(self, filename, password):
data = self._read_private_key_file('RSA', filename, password)

+ if not data:
+ return
if limited:
print self.hash
return

Post by Frank Dittrich
Apparently, both formats are able to crack the same input file after
converting it using the right tool. But ssh-ng is much faster.

Yes, ssh-ng is fast :-)

Post by Frank Dittrich
Why does ssh-ng have the "False positives possible" flag set?

ssh-ng does partial decryption and partial ASN decoding, hence it can
have false positives.

Post by Frank Dittrich
If ssh can avoid false positives, ssh-ng should be able to avoid false
positives as well, no?

You are right. We can have a 100% solid verification check in ssh-ng
format as well (and then remove FMT_NOT_EXACT from ssh-ng format).

Post by Frank Dittrich
$ ls -l ssh*test
-rw-rw-r--. 1 fd fd 2425 Jan 24 15:51 sshng-test
-rw-rw-r--. 1 fd fd 3505 Jan 24 15:51 ssh-test
doesn't look like ssh2john is extracting less information from the
keyfile than sshng2john is.
So, shouldn't ssh-ng be able to "understand" and convert $ssh2$ hashes?
What about ssh understanding the $sshng$ hashes?

IMO, we only care about ssh-ng being able to "understand" old-style
$ssh2$ hashes. Yes, this is possible and at some point I might have
promised Solar to implement such a feature ;)

Post by Frank Dittrich
Why do we even need two different tags?
Why different format names?

ssh format is well tested and been proven to work whereas ssh-ng is
highly experimental (but faster). So both formats currently co-exist.

Post by Frank Dittrich
Can't ssh-ng report "SSH RSA / DSA" instead of "ssh-ng SSH RSA / DSA"?
This would allow to pick the fastest of several benchmarks for
performance comparison in relbench.
(Of course, the format name should only be changed if both formats
understand the same canonical hash representation and if ssh-ng doesn't
produce false positives.)

ssh-ng *might* produce false positives (but it hasn't so far!) and
making ssh-ng understand old-style hashes requires more work (i.e.
patches welcome).

Hence, for now, it is better to treat them as separate formats.

Post by Frank Dittrich
What am I missing here?

I hope that I have answered your questions. Thanks for the feedback.

[Frank Dittrich]

Post by Dhiru Kholia
On Thu, Jan 24, 2013 at 8:50 PM, Frank Dittrich

Post by Frank Dittrich
This would allow to pick the fastest of several benchmarks for
performance comparison in relbench.
(Of course, the format name should only be changed if both formats
understand the same canonical hash representation and if ssh-ng doesn't
produce false positives.)

ssh-ng *might* produce false positives (but it hasn't so far!) and
making ssh-ng understand old-style hashes requires more work (i.e.
patches welcome).
Hence, for now, it is better to treat them as separate formats.

But once ssh-ng makes sure it doesn't produce false positives anymore,
it will still be much faster (except when the ratio of password
candidates to correct passwords is close to 1), right?

If so, at some point in the future, the old ssh format can be dropped
(or moved to unused), and ssh-ng will become the new ssh, right?

Frank

[Dhiru Kholia]

Post by Frank Dittrich

Post by Dhiru Kholia
On Thu, Jan 24, 2013 at 8:50 PM, Frank Dittrich

Post by Frank Dittrich
This would allow to pick the fastest of several benchmarks for
performance comparison in relbench.
(Of course, the format name should only be changed if both formats
understand the same canonical hash representation and if ssh-ng doesn't
produce false positives.)

ssh-ng *might* produce false positives (but it hasn't so far!) and
making ssh-ng understand old-style hashes requires more work (i.e.
patches welcome).
Hence, for now, it is better to treat them as separate formats.

But once ssh-ng makes sure it doesn't produce false positives anymore,
it will still be much faster (except when the ratio of password
candidates to correct passwords is close to 1), right?
If so, at some point in the future, the old ssh format can be dropped
(or moved to unused), and ssh-ng will become the new ssh, right?

Yes, that's right.

[magnum]

Post by Dhiru Kholia
On Thu, Jan 24, 2013 at 8:50 PM, Frank Dittrich

Post by Frank Dittrich
Can't ssh-ng report "SSH RSA / DSA" instead of "ssh-ng SSH RSA / DSA"?
This would allow to pick the fastest of several benchmarks for
performance comparison in relbench.
(Of course, the format name should only be changed if both formats
understand the same canonical hash representation and if ssh-ng doesn't
produce false positives.)

ssh-ng *might* produce false positives (but it hasn't so far!) and
making ssh-ng understand old-style hashes requires more work (i.e.
patches welcome).
Hence, for now, it is better to treat them as separate formats.

They should be separate formats in Jumbo, but I agree with Frank they could still be "one" format in relbench.

magnum (marketing dept.)

[Frank Dittrich]

Post by magnum

Post by Dhiru Kholia
On Thu, Jan 24, 2013 at 8:50 PM, Frank Dittrich

Post by Frank Dittrich
Can't ssh-ng report "SSH RSA / DSA" instead of "ssh-ng SSH RSA / DSA"?
This would allow to pick the fastest of several benchmarks for
performance comparison in relbench.
(Of course, the format name should only be changed if both formats
understand the same canonical hash representation and if ssh-ng doesn't
produce false positives.)

ssh-ng *might* produce false positives (but it hasn't so far!) and
making ssh-ng understand old-style hashes requires more work (i.e.
patches welcome).
Hence, for now, it is better to treat them as separate formats.

They should be separate formats in Jumbo, but I agree with Frank they could still be "one" format in relbench.

As long as ssh doesn't understand ssh-ng hashes and vice versa, there is
a risk of duplicate effort (cracking hashes which have already been
cracked using the other format).
If someone implements a prepare() for ssh-ng so that this format
understands the old ssh hash representation, we might want to move
john_register_one(&fmt_ssh);
up, so that it is registered before the plugin formats, *if* ssh-ng
really is still experimental.
That it can produce false positives is not that much of a problem,
provided the probability of false positives is very small.
(Did anybody compute that probability?)
Because of FMT_NOT_EXACT, john will not remove that hash once the first
match is found.
And you can still use --format=ssh to verify the password.

Frank

[magnum]

Post by Frank Dittrich
That it can produce false positives is not that much of a problem,
provided the probability of false positives is very small.
(Did anybody compute that probability?)
Because of FMT_NOT_EXACT, john will not remove that hash once the first
match is found.
And you can still use --format=ssh to verify the password.

I had a look at check_padding_3des() that verifies the result. It's hard to calculate a probability. The padding check might give false *negatives* unless there always is padding present even for blocks that happened to be aligned. But it looks to me it would be a pretty freaking unreal coincidence if it ever made a false positive. If you ask me (but you shouldn't), we could remove the FMT_NOT_EXACT flag.

Can't you batch creation of a million test files and try cracking them? That's what I did with RAR. It's a pity key file creation is so slow :-)

BTW I just committed an unrelated fix to that format.

magnum

[Frank Dittrich]

Post by magnum
I had a look at check_padding_3des() that verifies the result. It's hard to calculate a probability. The padding check might give false *negatives* unless there always is padding present even for blocks that happened to be aligned. But it looks to me it would be a pretty freaking unreal coincidence if it ever made a false positive. If you ask me (but you shouldn't), we could remove the FMT_NOT_EXACT flag.

Is that "false negatives" as in "john might fail to recognize that a
candidate matches the hash"?
This would be really bad. ssh-ng would need to be orders of magnitude
faster than ssh to be useful despite such a problem.
IMHO, it would be unfair to compare the performance of a format which
might miss candidates with the performance of a format which doesn't.


Also, these 2 comments don't look like inspiring confidence:
if(pad > 16) /* FIXME: is this check valid? */
// "Bad padding byte. You probably have a wrong password"
return -1;


and

/* FIXME: now this integer has to be big, is this always true? */

Frank

[magnum]

Post by Frank Dittrich

Post by magnum
I had a look at check_padding_3des() that verifies the result. It's hard to calculate a probability. The padding check might give false *negatives* unless there always is padding present even for blocks that happened to be aligned. But it looks to me it would be a pretty freaking unreal coincidence if it ever made a false positive. If you ask me (but you shouldn't), we could remove the FMT_NOT_EXACT flag.

Is that "false negatives" as in "john might fail to recognize that a
candidate matches the hash"?

Yes. The format assumes that padding is always applied (by any fork of any version of ssh, ideally including future ones) even when the data is block aligned without it (a pad-only block is added). Maybe this is a perfectly valid assumption because it is specified somewhere, I do not know. If it's just based on observations, it is dangerous. I believe this kind of padding check is pretty common. If it's in the specifications, everything is OK.

Post by Frank Dittrich
This would be really bad. ssh-ng would need to be orders of magnitude
faster than ssh to be useful despite such a problem.
IMHO, it would be unfair to compare the performance of a format which
might miss candidates with the performance of a format which doesn't.

Yes. False negatives are the absolute worst (by far) bug that can ever hit us. A format with known false negatives would go straight to unused. I can live with false positives.

Post by Frank Dittrich
if(pad > 16) /* FIXME: is this check valid? */
// "Bad padding byte. You probably have a wrong password"
return -1;

It is a valid check provided the initial assumption is correct.

Post by Frank Dittrich
and
/* FIXME: now this integer has to be big, is this always true? */

Yes, that is worrisome. So Dhiru is probably right we should keep the old format, and have this one with lower precedence.

magnum

[Dhiru Kholia]

Post by magnum
Yes. The format assumes that padding is always applied (by any fork of any version of ssh, ideally including future ones) even when the data is block aligned without it (a pad-only block is added). Maybe this is a perfectly valid assumption because it is specified somewhere, I do not know. If it's just based on observations, it is dangerous. I believe this kind of padding check is pretty common. If it's in the specifications, everything is OK.

This padding length check is based on observations and prior experience ;)

Post by magnum

Post by Frank Dittrich
if(pad > 16) /* FIXME: is this check valid? */
// "Bad padding byte. You probably have a wrong password"
return -1;

It is a valid check provided the initial assumption is correct.

BTW, this check is borrowed from Apple Keychain format.

Post by magnum

Post by Frank Dittrich
/* FIXME: now this integer has to be big, is this always true? */

Yes, that is worrisome. So Dhiru is probably right we should keep the old format, and have this one with lower precedence.

I wouldn't worry too much about this check.

RSA (as used in ssh) uses *big* prime numbers, correct?. In addition,
ssh-keygen places a minimum key-bits length restriction.

[magnum]

Post by Dhiru Kholia

Post by magnum
Yes. The format assumes that padding is always applied (by any fork of any version of ssh, ideally including future ones) even when the data is block aligned without it (a pad-only block is added). Maybe this is a perfectly valid assumption because it is specified somewhere, I do not know. If it's just based on observations, it is dangerous. I believe this kind of padding check is pretty common. If it's in the specifications, everything is OK.

This padding length check is based on observations and prior experience ;)

Post by magnum

Post by Frank Dittrich
if(pad > 16) /* FIXME: is this check valid? */
// "Bad padding byte. You probably have a wrong password"
return -1;

It is a valid check provided the initial assumption is correct.

BTW, this check is borrowed from Apple Keychain format.

Post by magnum

Post by Frank Dittrich
/* FIXME: now this integer has to be big, is this always true? */

Yes, that is worrisome. So Dhiru is probably right we should keep the old format, and have this one with lower precedence.

I wouldn't worry too much about this check.
RSA (as used in ssh) uses *big* prime numbers, correct?. In addition,
ssh-keygen places a minimum key-bits length restriction.

Sounds all good to me then. Maybe the FIXME should be changed to a comment on what it actually is testing.

magnum

[Frank Dittrich]

Post by magnum
Can't you batch creation of a million test files and try cracking them? That's what I did with RAR. It's a pity key file creation is so slow :-)

On my laptop (Intel(R) Core(TM) i3-2367M CPU @ 1.40GHz):

$ time ( for i in `seq 1 100`; do ssh-keygen -t rsa -f
/home/fd/.ssh/id_rsa_000-test$i -P test$i -N test$i > /dev/null ; done )

real 0m31.321s
user 0m30.490s
sys 0m0.532s
$ time ( for i in `seq 101 1100`; do ssh-keygen -t rsa -f
/home/fd/.ssh/id_rsa_000-test$i -P test$i -N test$i > /dev/null ; done )

real 4m51.946s
user 4m44.037s
sys 0m5.550s

(BTW: ssh-keygen requires a minimum password length of 5. But I don't
know if this is true for all versions.)

That means about 0.3 seconds per key, or almost 3.5 days for 1 million keys.
CPU doesn't seem to be the bottleneck.
More probably, the system is running out of entropy.

john cracked all 1100 passwords immediately in single mode after
converting them using
$ ./sshng2john.py /home/fd/.ssh/id_rsa_000-test*[0-9] > sshng-test


Frank

[Dhiru Kholia]

On Fri, Jan 25, 2013 at 5:18 AM, Frank Dittrich

Post by Frank Dittrich

Post by magnum
Can't you batch creation of a million test files and try cracking them? That's what I did with RAR. It's a pity key file creation is so slow :-)

john cracked all 1100 passwords immediately in single mode after
converting them using
$ ./sshng2john.py /home/fd/.ssh/id_rsa_000-test*[0-9] > sshng-test

ssh formats have their own mini test-suite.

See http://openwall.info/wiki/_media/john/ssh-key-collection.tar.bz2

AFAIK ssh-ng does not have false-negatives problem.

[magnum]

Post by Dhiru Kholia
On Thu, Jan 24, 2013 at 8:50 PM, Frank Dittrich

Post by Frank Dittrich
$ ./sshng2john.py id_rsa > sshng-test
(BTW: I had to install python-crypto on Fedora 18 to make the script work.)

Can you please test the following patch to see if it makes things better?
diff --git a/run/sshng2john.py b/run/sshng2john.py
index 12a6f60..b08a85e 100755
--- a/run/sshng2john.py
+++ b/run/sshng2john.py

I have problems with sshng2john on OSX but I can't get that patch to apply. Please commit it, or re-post it as an attachment.

magnum