Nem is kell őket lecserélni. Nincs olyan ismert támadás, ami egy meglévő md5 lenyomathoz képes lenne másik, helyes X509 struktúrájú tanúsítványt kiszámolni. A legerősebb ismert támadás (már 2007 óta) az ún. Chosen-Prefix Collision, ahol egyszerre kell számolni, s változtatni a két adathalmaz adott részét. Ez egy még most is MD5-tel ÚJ tanúsítványt kiadó CA ellen elég lehet (ha egyéb feltétek is fennállnak... lásd lent)
Az MS cikk nem mond részleteket, de mivel az algoritmust megemlítik, ezért a H-Security azt gyanítja, hogy csak az aláírást vitték át:
http://www.h-online.com/security/news/item/Flame-worm-was-signed-by-for…
"an attacker can transfer the Microsoft signature from a legitimate Terminal Server certificate to his fraudulent code signing certificate"
Ha ez történt, akkor ugyanúgy tudtak hamis certet csinálni, mint ahogy anno csináltak egy köztes CA-t 2008-ban a RapidSSL online szolgáltatását használva. Ahhoz akkor a kutatók előre számoltak ütköző párokat (épp ezért nem is sikerült elsőre, mert pl. az időzítés s máshonnan jövő kérések elhasználták az előre kiszámolt cert sorszámot): http://www.phreedom.org/research/rogue-ca/md5-collisions-1.0.ppt
UPDATE: A pár hozzászólással lejjebb idézett cikkben ugyanezek a kutatók megerősítik, hogy az md5 Chosen-Prefix Collision volt az alapja a Flamerhez használt sikeres cert készítésnek, de egy teljesen új (vagy akár az általuk közöltnél régebbi), a lényeg: más módszerrel.