sshd is treating certificate extensions as critical and is disallowing logins using certificates with unknown extensions. This is happening with v01 certificates and actually the bug is quite obvious when looking for it in the code.

While I am abusing this feature somewhat to encode additional data in a certificate such that it is covered by the certificate's signature this bug has the more serious side effect that it will break backwards compatibility in the future. If OpenSSH adds new cert extensions in a new version older versions of sshd (all versions prior to 6.8) will reject those certificates even though the extensions are supposed to be optional.

Here's a sample certificate's ssh-keygen output:

        Type: ssh-rsa-cert-v01@openssh.com user certificate
        Public key: RSA-CERT 1c:fd:36:27:db:48:3f:ad:e2:fe:55:45:67:b1:47:99
        Signing CA: RSA 62:af:90:1b:ef:b1:5a:c9:e0:2a:be:8b:3e:a9:25:18
        Key ID: "bvanzant+stage@brkt.com"
        Serial: 1
        Valid: from 2015-04-21T07:09:30 to 2015-04-21T09:11:30
        Principals:
                ec2-user
                ubuntu
        Critical Options: (none)
        Extensions:
                ca-environment UNKNOWN OPTION (len 5)
                ca-reason UNKNOWN OPTION (len 17)
                permit-agent-forwarding
                permit-port-forwarding
                permit-pty

Notice the two non-standard extensions. When I attempt to use this certificate sshd logs:

sshd[30925]: error: Certificate critical option "ca-environment" is not supported

The relevant code is at lines 597 and 603 of auth-options.c http://cvsweb.openbsd.org/cgi-bin/cvsweb/src/usr.bin/ssh/auth-options.c?annotate=1.65

Notice the fourth parameter is set to 1 in both the critical and extensions cases. This tells parse_option_list to treat the things being parsed as critical. I believe that the call on line 603 should have crit set to 0.