I imagine it was falling back to legacy user verification because it could not find the cross-signing keys for the user it was going to verify. Federation bug? Ftr, we don't cross-sign when doing legacy verification because we haven't verified the MSK for the other user, only their device key, which we can't sign.

There is a bug that legacy trust doesn't get counted when aggregating the trust of all devices for a user, which apparently was deemed not a problem. When expanding the session section in user info @ara4n, was the device you verified marked green at least?

The logs from @matthew:arasphere.net indeed show this right before starting the verification request:

2020-04-16T12:33:49.346Z I got cross-signing keys for @matthewtest401:matrix.org: {}

When quering keys now (from matrix.org) for @matthewtest401:matrix.org I get a master key of dn699wr2FITbozlGId4YH8vsb+BlhYC/AuJzo34/aCs.

When expanding the session section in user info @ara4n, was the device you verified marked green at least?

Yes:

This feels related to #12973 and matrix-org/synapse#7276 then.

see also #13248

I experiment that problem too as I was explaining in here : #13566

My shield is green on his devices but his shield keep being black on my devices (both Riot-desktop and RiotX). I have all his devices verified though (legacy way)... but I can still start a cross-signing verification with him from Riot-desktop (he can't) that won't lead to a better situation. It will say that it succeeded but his shield will remain black.

@Thatoo can you please file a separate issue and submit your debug logs from "help & about" in the settings?

I have done it in here : #13824
Thank you for your help.