My company admin just found the answer to this question as I was writing it, so I'm posting it here for others:
I use xfreerdp to connect to a Windows 7 machine from Linux with RDP. Typically, I provide my credentials and the IP address of the machine and everything works fine. One day, I come in and attempt to connect, only to be presented with this:
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that a host key has just been changed.
The fingerprint for the host key sent by the remote host is
xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx
(The x's were actual numbers.) I checked my Linux known_hosts file for the machine I was connecting to, and yes, indeed, the RSA fingerprint for the machine did change. So I asked the admin at my company if he had done some updates or anything that would have changed the key Windows uses for RDP sessions. He said nothing had changed that he was aware of. At this point, common sense and my knowledge of security tells me I wasn't supposed to connect until I logged into the machine physically and checked that there was indeed a new RSA host key for RDP. (If there wasn't, then it would be likely that there was a man-in-the-middle attack going on.)
The problem is, when I logged into the physical machine to find out if the RSA key had changed, I couldn't figure out where to go to view it. I searched online and couldn't figure out any way in Windows 7 to view the RSA fingerprint of the key RDP sessions use. Does anyone know where I can view the key?
Here is a step by step guide on how to obtain your RSA host key fingerprint for RDP sessions in Windows 7:
First, click on the start button (or press the Windows key on the keyboard). Type "mmc" into the search, and select "mmc.exe" (Microsoft Management Console).
When it opens, click File->Add/Remove Snap-in... From the list on the left (Available snap-ins), select "Certificates" and click "Add >"
Select "Computer account" click next. Make sure "Local computer" is selected, and click "Finish". Click "OK" to exit the Add/Remove Snap-in screen.
Now you should be back in the main MMC window, but there should be a Snap-in called "Certificates (Local Computer)" in the list on the left. Expand that and expand "Remote Desktop" and then "Certificates". There should be at least one certificate that appears in the middle area of the window. Double click on that, and select the "Details" tab. Scroll down to the bottom and there will be details about the key specified in the certificate, including the "Thumbprint" field, which corresponds to the host key fingerprint that Linux's xfreerdp reports when you attempt to connect to the machine.
You'll also notice that there's an additional two hex digits in the "Thumbprint" field. (The xfreerdp-reported fingerprint is 38 hex digits long, while the thumbprint field has 40). Strip off the first two hex digits in the thumbprint to obtain the RSA fingerprint of the RDP host key (I have no idea what these digits are).