You either authorize using certificates with identities (-I) or using public keys. You should not mix both of them.
Can you clarify exact configuration what are you using on your server and client and exact commands what you are running (and preferably also the logs?). From this report I have no idea how to reproduce your problem nor how to fix that.

"You either authorize using certificates with identities (-I) or using public keys. You should not mix both of them."

Why not? 

We have a series of appliances that have no "users" on them. We ssh to them using keys that expire. The key identifier allows us to track who logs on them. The / and /usr file systems are read-only and check-sum'ed. We do not add or remove users.

We create a central key authority, here is an example:
markw@engwifi-230-242:~/repro$ cat bootstrap.sh 
#!/bin/sh

export DEMO_CA_DIR="/home/somedir/repro/ssl"

rm -rf $DEMO_CA_DIR
mkdir -m 0755  $DEMO_CA_DIR 
mkdir -m 0755  $DEMO_CA_DIR/private 
mkdir -m 0755  $DEMO_CA_DIR/certs 
mkdir -m 0755  $DEMO_CA_DIR/newcerts 
mkdir -m 0755  $DEMO_CA_DIR/crl

export DEMO_CA_KEY=$DEMO_CA_DIR/private/demo.key
export DEMO_CA_PEM=$DEMO_CA_DIR/private/demo.pem
export DEMO_CA_CRT=$DEMO_CA_DIR/certs/demo.crt
export DEMO_CA_SSH=$DEMO_CA_DIR/certs/demo.ssh

SSH_KEYGEN=$SSHPATH/ssh-keygen

#
# Initialize the private/public key infrastructre
#
REPLACE=$(echo $DEMO_CA_DIR | sed  's/\//\\\//g')
cat openssl.cnf | sed s/DEMO_CA_DIR/$REPLACE/ > $DEMO_CA_DIR/openssl.cnf

# Create an empty index file
#
touch $DEMO_CA_DIR/index.txt

#
# The serial numbers should start at 01
#
echo "01" > $DEMO_CA_DIR/serial

#
# Create the certificate authority
#
openssl req -config $DEMO_CA_DIR/openssl.cnf -nodes -new -x509 -extensions v3_ca -keyout $DEMO_CA_KEY  -subj '/CN=demo.noname'  -out $DEMO_CA_CRT -days 100 

#
# Mark it as only usable by us
chmod 0600 $DEMO_CA_KEY

#
# Create the SSH public key
#
ssh-keygen -f $DEMO_CA_KEY -y > $DEMO_CA_SSH

#
# Create a PEM file for signinging
#
cat $DEMO_CA_CRT $DEMO_CA_KEY > $DEMO_CA_PEM
chmod 0600 $DEMO_CA_PEM


######
markw@engwifi-230-242:~/repro$ cat ssh_create_user.sh 
#!/bin/sh
export DEMO_CA_DIR="/home/somedir/repro/ssl"
export DEMO_CA_KEY=$DEMO_CA_DIR/private/demo.key
export DEMO_CA_PEM=$DEMO_CA_DIR/private/demo.pem
export DEMO_CA_CRT=$DEMO_CA_DIR/certs/demo.crt
export DEMO_CA_SSH=$DEMO_CA_DIR/certs/demo.ssh

ssh-keygen -f $1-key
ssh-keygen -s $DEMO_CA_PEM -C "$1" -I "$1" -n $1,root -V +3d $1-key.pub 
#######

Now, run bootstrap.sh, this will create your central authority.
Copy ssl/certs/demo.ssh to /etc/ssh to your target machine or VM
Add this line to the target  sshd_config 
TrustedUserCAKeys	/etc/ssh/demo.ssh

Restart sshd on your target machine

make sure:
#session    required     pam_namespace.so
is commented out in the target's /etc/pam.d/sshd

on your CA machine, in the repro directory

bash ssh_create_user.sh fubar
<use empty passphrases if you like>

ssh -i fubar-key root@target

You should connect.

Now, uncomment this line on the target: (/etc/pam.d/sshd)
session    required     pam_namespace.so 

Try again on your CA machine:
ssh -i fubar-key root.122.188

It will fail.

There is no prescription that the key_identity MUST be a valid user on the target machine.

Created attachment 1173489 [details]
Tar file of scripts

This will make it easy to reproduce

Thank you for verbose information about reproducer.

You reported the bug against RHEL6, which is using openssh-5.3, but it is using 

   [-n principals]

instead of

   [-Z principals]

in RHEL6 environment. But it should not make a difference in the end.

I tried to reproduce your described behavior according to your description, but without any success. I am able to connect to root account with this key generated (on RHEL6 machine). There will be probably also some different configuration in place.

Can you check what is in your  /etc/security/namespace.conf  and why? If this one is empty, the  pam_namespace.so  in PAM stack should be noop. Polyinstantiation should also require SELinux boolean  allow_polyinstantiation. Do you have that enabled or can you see some AVCs in audit?

Mark, could you have a look in the questions I asked in the comment #5? I can't reproduce your behavior in my testing system, which proposes there is some other effective configuration in your system. Otherwise I will close this bug soon.

    Thank you for taking the time to enter a bug report with us. We appreciate the feedback and look to use reports such as this to guide our efforts at improving our products. That being said, this bug tracking system is not a mechanism for requesting support, and we are not able to  guarantee the timeliness or suitability of a resolution.

    If this issue is critical or in any way time sensitive, please raise a ticket through your regular Red Hat support channels to make certain  it receives the proper attention and prioritization to assure a timely resolution. 

    For information on how to contact the Red Hat production support team, please visit:

    https://access.redhat.com/support/

The needinfo request[s] on this closed bug have been removed as they have been unresolved for 1000 days