Questions about inferred state machines for OpenSSH

[P. V.]

Dear all,

For my thesis, I've been working on automatic inference of state
machines for SSH servers. I ran into a couple of particularities
regarding OpenSSH's inferred state machine, and was hoping some of you
might be interested. Maybe you can even shed some light on it.

Setup: I'm using LearnLib's (Java) version of the L* learning
algorithm [1] to come up with sequences of textual representations of
SSH messages (such as "DEBUG; DISCONNECT"). An altered version of
Paramiko (Python) receives those queries and translates them to actual
SSH traffic, which is sent to OpenSSH. Responses are fed to the
learning algorithm, resulting in a state machine.

The PDFs of inferred state machines, as well as the used messages, can
be found online [2]. I've queried the the transport layer, user
authentication layer and connection layer separately.

Now for my questions. Assuming my results are correct, it seems that:
1) OpenSSH is extremely liberal when it comes to exchanging kexinit
messsages (openssh-localhost-L1.pdf). It allows entering a key
exchange without receiving a proper kexinit message at all. Since this
message is required to exchange parameters, does this imply that
OpenSSH will guess those when no kexinit is received?

2) OpenSSH does not allow rekeying until after correct user
authentication. The RFCs specify otherwise. Is this a deliberate
choice?

3) OpenSSH shows peculiar behavior in user re-authentication. Some
re-authentication methods seem to be disallowed after an unsuccessful
authentication attempt. You can see what I mean in
openssh-localhost-L2.pdf. Is this intended behavior, a bug, or perhaps
an error on my side?

4) Unlike other tested SSH servers, OpenSSH seems to close the entire
connection (rather than close the channel) on a channel-close message
in certain conditions. This results in the 'has_commands' and
'has_commands_pty' states in openssh-localhost-L3.pdf. I was wondering
why. An error on my side, or intended behavior?

I'd be more than happy to hear what you think about the results.
Please let me know if you need any further information! I can also
share a conceptual version of my thesis for those interested.

Kind regards, Patrick

[1] http://sp09.pbworks.com/f/LearningJournal.pdf
[2] https://drive.google.com/folderview?id=0B6T2_FvFKPIkRGdqVDFtOXNQQWc

[Damien Miller]

Post by P. V.
Dear all,
For my thesis, I've been working on automatic inference of state
machines for SSH servers. I ran into a couple of particularities
regarding OpenSSH's inferred state machine, and was hoping some of you
might be interested. Maybe you can even shed some light on it.
Setup: I'm using LearnLib's (Java) version of the L* learning
algorithm [1] to come up with sequences of textual representations of
SSH messages (such as "DEBUG; DISCONNECT"). An altered version of
Paramiko (Python) receives those queries and translates them to actual
SSH traffic, which is sent to OpenSSH. Responses are fed to the
learning algorithm, resulting in a state machine.
The PDFs of inferred state machines, as well as the used messages, can
be found online [2]. I've queried the the transport layer, user
authentication layer and connection layer separately.
1) OpenSSH is extremely liberal when it comes to exchanging kexinit
messsages (openssh-localhost-L1.pdf). It allows entering a key
exchange without receiving a proper kexinit message at all. Since this
message is required to exchange parameters, does this imply that
OpenSSH will guess those when no kexinit is received?

I'm not sure what you mean by "entering a key exchange without receiving
a proper kexinit message" because key exchange is initiated by a kexinit
message. Do you mean that method specific messages are accepted before
KEXINIT? (I can't see how this can happen from looking at the code).

Post by P. V.
2) OpenSSH does not allow rekeying until after correct user
authentication. The RFCs specify otherwise. Is this a deliberate
choice?

I don't think this is the case, it is true that ssh/sshd
fail to apply rekeying limits before completion of userauth but I
think they will respond to KEXINIT messages.

Post by P. V.
3) OpenSSH shows peculiar behavior in user re-authentication. Some
re-authentication methods seem to be disallowed after an unsuccessful
authentication attempt. You can see what I mean in
openssh-localhost-L2.pdf. Is this intended behavior, a bug, or perhaps
an error on my side?

Not sure what you mean here, but we don't support re-authentication
(as I understand the term). Do you mean subsequent authentication
requests after a "partial" authentication success, authentication
requests after a failed request or something different?

We certainly shouldn't allow requesting the userauth service after
userauth has completed.

Post by P. V.
4) Unlike other tested SSH servers, OpenSSH seems to close the entire
connection (rather than close the channel) on a channel-close message
in certain conditions. This results in the 'has_commands' and
'has_commands_pty' states in openssh-localhost-L3.pdf. I was wondering
why. An error on my side, or intended behavior?

It would be helpful to see debug messages from ssh/sshd for this case
(well, all cases but this in particular).

-d

[P. V.]

Hi Damien,

Thanks for your reply. I really appreciate you taking the time to
investigate this.

I will try to clarify some things.

Post by Damien Miller
I'm not sure what you mean by "entering a key exchange without receiving
a proper kexinit message" because key exchange is initiated by a kexinit
message. Do you mean that method specific messages are accepted before
KEXINIT? (I can't see how this can happen from looking at the code).

Attached (log1) you find the OpenSSH debug log for a sequence in which
I manually send the sequence "SSH_MSG_KEXDH_INIT; SSH_MSG_KEXDH_INIT;
SSH_MSG_NEWKEYS". A normal key exchange sequence would be
"SSH_MSG_KEXINIT; SSH_MSG_KEXDH_INIT; SSH_MSG_NEWKEYS". Unless there
is an error in my code, it seems that OpenSSH does accept this anyway.

Post by Damien Miller
Jan 27 11:19:31 desktop sshd[4066]: debug1: SSH2_MSG_KEXINIT received [preauth]

while it didn't receive a KEXINIT but a KEXDH_INIT.

Same goes for a sequence such as: "SSH_MSG_IGNORE; SSH_MSG_KEXDH_INIT;
SSH_MSG_NEWKEYS". Instead of receiving a KEXINIT, the server receives
an IGNORE but continues with the key exchange anyway.

This only applies to the messages the server receives, it always
correctly sends an KEXINIT upon connection.

Post by Damien Miller
I don't think this is the case, it is true that ssh/sshd
fail to apply rekeying limits before completion of userauth but I
think they will respond to KEXINIT messages.

I sent the following message sequence to the server: "SSH_MSG_KEXINIT;
SSH_MSG_KEXDH_INIT; SSH_MSG_NEWKEYS; SSH_MSG_SERVICE_REQUEST;
SSH_MSG_NEWKEYS". It behaves normally up until the point that I
initiate a key re-exchange (last message). The SSH server returns an
SSH_MSG_UNIMPLEMENTED and closes the connection. Log2 gives the debug
output.

The sequence "SSH_MSG_KEXINIT; SSH_MSG_KEXDH_INIT; SSH_MSG_NEWKEYS;
SSH_MSG_SERVICE_REQUEST; SSH_MSG_USERAUTH_REQUEST; SSH_MSG_NEWKEYS;
SSH_MSG_KEXDH_INIT; SSH_MSG_NEWKEYS" performs a kex-exchange,
authentication and another key exchange. This does work as expected.
Log3 gives the debug output.

Again, I can't exclude a programming error on my side, but it seems
that rekeying does not work until after successful user
authentication.

Post by Damien Miller
Not sure what you mean here, but we don't support re-authentication
(as I understand the term). Do you mean subsequent authentication
requests after a "partial" authentication success, authentication
requests after a failed request or something different?
We certainly shouldn't allow requesting the userauth service after
userauth has completed.

Forgive my ambiguity, I meant authentication requests after an earlier
failed authentication request. Debug log gives the answer however, I
tried the other methods with another username. This is apparently not

Post by Damien Miller
Jan 27 12:01:07 desktop sshd[4845]: Disconnecting: Change of username or service not allowed: (NOACCESS,ssh-connection) -> (thesis,ssh-connection) [preauth]
It would be helpful to see debug messages from ssh/sshd for this case
(well, all cases but this in particular).

I sent the following sequence to the OpenSSH server.

SSH_MSG_KEXINIT;
(server replies with SSH_MSG_KEXINIT)
SSH_MSG_KEXDH_INIT;
(server replies with SSH_MSG_KEXDH_REPLY)
SSH_MSG_NEWKEYS;
(server does not reply)
SSH_MSG_SERVICE_REQUEST;
(server replies with SSH_MSG_SERVICE_ACCEPT)
SSH_MSG_USERAUTH_REQUEST
(server replies with SSH_MSG_USERAUTH_SUCCESS and SSH_MSG_GLOBAL_REQUEST)
SSH_MSG_CHANNEL_OPEN
(server replies with SSH_MSG_CHANNEL_OPEN_CONFIRMATION)

-- Now I do a rekey --
SSH_MSG_KEXINIT;
(server replies with SSH_MSG_KEXINIT)
SSH_MSG_KEXDH_INIT;
(server replies with SSH_MSG_KEXDH_REPLY)
SSH_MSG_NEWKEYS;
(server does not reply)

-- Now I close the channel --

SSH_MSG_CHANNEL_CLOSE
(server replies with SSH_MSG_CHANNEL_CLOSE and sends an SSH_MSG_DISCONNECT)

The entire debug log can be found in the log4 attachment.

Hope this clarifies everything. I would love to hear your thoughts on
these issues!

Kind regards,

[1] https://drive.google.com/drive/folders/0B6T2_FvFKPIkRGdqVDFtOXNQQWc

Post by Damien Miller

Post by P. V.
Dear all,
For my thesis, I've been working on automatic inference of state
machines for SSH servers. I ran into a couple of particularities
regarding OpenSSH's inferred state machine, and was hoping some of you
might be interested. Maybe you can even shed some light on it.
Setup: I'm using LearnLib's (Java) version of the L* learning
algorithm [1] to come up with sequences of textual representations of
SSH messages (such as "DEBUG; DISCONNECT"). An altered version of
Paramiko (Python) receives those queries and translates them to actual
SSH traffic, which is sent to OpenSSH. Responses are fed to the
learning algorithm, resulting in a state machine.
The PDFs of inferred state machines, as well as the used messages, can
be found online [2]. I've queried the the transport layer, user
authentication layer and connection layer separately.
1) OpenSSH is extremely liberal when it comes to exchanging kexinit
messsages (openssh-localhost-L1.pdf). It allows entering a key
exchange without receiving a proper kexinit message at all. Since this
message is required to exchange parameters, does this imply that
OpenSSH will guess those when no kexinit is received?

I'm not sure what you mean by "entering a key exchange without receiving
a proper kexinit message" because key exchange is initiated by a kexinit
message. Do you mean that method specific messages are accepted before
KEXINIT? (I can't see how this can happen from looking at the code).

Post by P. V.
2) OpenSSH does not allow rekeying until after correct user
authentication. The RFCs specify otherwise. Is this a deliberate
choice?

I don't think this is the case, it is true that ssh/sshd
fail to apply rekeying limits before completion of userauth but I
think they will respond to KEXINIT messages.

Post by P. V.
3) OpenSSH shows peculiar behavior in user re-authentication. Some
re-authentication methods seem to be disallowed after an unsuccessful
authentication attempt. You can see what I mean in
openssh-localhost-L2.pdf. Is this intended behavior, a bug, or perhaps
an error on my side?

Not sure what you mean here, but we don't support re-authentication
(as I understand the term). Do you mean subsequent authentication
requests after a "partial" authentication success, authentication
requests after a failed request or something different?
We certainly shouldn't allow requesting the userauth service after
userauth has completed.

Post by P. V.
4) Unlike other tested SSH servers, OpenSSH seems to close the entire
connection (rather than close the channel) on a channel-close message
in certain conditions. This results in the 'has_commands' and
'has_commands_pty' states in openssh-localhost-L3.pdf. I was wondering
why. An error on my side, or intended behavior?

It would be helpful to see debug messages from ssh/sshd for this case
(well, all cases but this in particular).
-d