Saturday, February 17, 2007

CPS2 not much left to do

When I originally wrote the key searching program, that was on the assumption that the key for the second Feistel network was 96 bits long.

Each (E,D) pair reduces the key space by a factor of about 216, so to isolate the correct key with good confidence one would need at least 96/16 = 6 (E,D) pairs.

The big problem is finding those pairs. Remember that they must be at compatible addresses, that is addresses whose bottom 17 bits are the same. This is a serious limitation, because the code of several games only covers a range of 0x80000 bytes, which would give a maximum of 4 pairs at any address. For the Super Puzzle Fighter 2 games, the range is just 0x40000 bytes, giving just 2 pairs per address.
One can find hundreds, even thousands of of (E,D) pairs, but if they are not at compatible addresses they are of no use to find the key using this attack.

However, now we know that the key actually has only 64 significant bits, some of which are repeated. I therefore rewrote the program to take that into account. This means that only 4 (E,D) pairs are needed to isolate the key.

Also, I made several important optimisations that I missed the first time around, like caching intermediate results and speeding up the s-boxes calculations by using precalculated tables (this last optimisation also made into MAME so the decryption when loading a game is now faster).

The end result is a program that is orders of magnitude faster than the previous one.
Now it takes just 15 seconds to find the key given 8 (E,D) pairs. With 5 pairs, which was just plain impossible before, it takes 5 minutes. With 4 pairs, 35 minutes.

These improvement made it simple to find most of the remaining keys, even for games that didn't have a matching revision already decrypted (most notably some of the Steeet Fighter Zero versions).

But there's more: the program is now fast enough to go one step further, and look for the key with just 3 pairs. Of course 3 pairs are not enough to isolate the right key: they only reduce the key space by about 248, therefore leaving about 216 keys which are compatible with the data. Once a 64-bit key for the second Feistel network is selected, the compatible 64-bit master keys can then be easily generated, and used to verify other (E,D) pairs at different addresses. This allows to find the correct key in less than one day, and I had to use this extended attack for a couple of the most problematic games.

In the meantime, Andreas Naive has been busy implementing the attack he had described on his blog, and was able to find the keys for two of the Super Puzzle Fighter 2 games. Unfortunately, the attack failed on the third. Work is still in progress on that one, and there is some hope that the key will eventually be found.

The only other games that are missing a key are the two CPS2 versions of Mega Man. There is no decrypted CPS2 version of that game to compare with, and the CPS1 version seems to be too different to be able to find good pairs.

12 comments:

o.broggini said...

Egregio dott. Salmoria,
mi chiamo Oliver Broggini e sono un giornalista del Corriere del Ticino (quotidiano della Svizzera italiana). Sull'edizione cartacea di domani, pubblicheremo una mia intervista a Matteo Bittanti sul tema del Digital game canon (se le interessa, da domani potrò inviargliela in formato .pdf). Frugando per la rete, sono poi venuto a conoscenza del suo progetto Mame e di alcune delle incredibili peripezie che ne hanno permesso la realizzazione. Se le interessa, vorrei proporle un'intervista a tutto tondo sull'iniziativa: mi risponda all'indirizzo o.broggini@gmail.com

L. Gioia said...

Egregio Dott. Salmoria,
sono un appassionato di Mame.
Sul vecchio computer che avevo avevo le versione mame32 da 0.60 alla 0.96 che giravano tutte bene (s.o. win98). Da 1 anno ormai ho un nuovo computer con winXP. Queste versioni su winXP non sono motlo stabili, spesso le roms vengono caricate ma non si vede il gioco (mentre con win98 si vedevano9, oppure mi va in crash il monitor, come devo fare? Scaricare una delle ultime versioni, o l'ultimissima mame32 0.119 potrebbe essere una soluzione?
Grazie per l'attenzione, ancora complimenti e lieto che l'inventore di questo emulatore che mi riporta indietro di 20 anni sia italiano come me. la mia e-mail è gioiallo@hotmail.com

Haze said...

Nicola> Just incase you didn't get my reply to your mail (03/12/07), Aaron says he DID reply to your original email, but it seems like your provider (and several others in Italy?) are silently blocking mail, including mail directly from him. Luca and Kale have reported a similar problem.

Daniele said...

Nicola,
scusami se ti do del tu, ma vorrei chiederti gentilmente se sei disposto a rilasciare una interview a tempo perso per il sito di collezionisti più grande d'europa.
www.gamescollection.it
Siamo una comunità di persone adulte, con la passione del retrogaming alla sua massima potenza, e di sicuro siamo spendaccioni :D
Ti prego, se sei interessato, fammi sapere qualcosa a daniele.fiorentini@gmail.com
Ho provato ad usare il form su MameDev ma non c'è verso di mandarti una mail, questa rimane la mia ultima chanche.
Per l'interview, niente di che, poche domande sul fenomeno arcade, visto e considerato che ogni membro della community in casa ha tonnellate di robe arcade...quindi condividiamo la passione.
Grazie infinte, che Dio ti benedica.
Daniele

LaughingOtter said...

G'day!

Love this MAME stuff! I've been with you guys since the beginning!

If you're the person who deals with the Genpei ToumaDen ROMsets, then you should know that under the Dip Switches menu, the first Unknown option, when set to On, allows you to select your opening stage after the introduction.

Not much, but it's a little something in return for all the years of fun you've given us!

Pavel said...

Hello Nicola!
I've found your blog using Google. Do you remember Amiga times?
I am a member of AROS development team (http://aros.org) and i'd like to ask you about MFS handler you wrote in 1995. Do you still have its source code somewhere? It would be very nice if you would allow us to use it as part of our system. Or at least tell us the alrogythm it uses.
Please contact me by email: sonic_amiga at rambler.ru
or:
pavel.fedin@gmail.com

Kind regards.

Luca B. said...

Salve Nicola

ci piacerebbe invitarti a Carpi (Mo) a fine dicembre all'interno di un festival di musica elettronica dove terremo dei seminari sul mondo dei videogiochi e della micromusic (quella branca della musica elettronica realizzata con vecchie console, gameboy, etc etc).

Per ulteriori informazioni e per spiegarti più precisamente il progetto puoi contattarmi alla mail
lucabenni@gmail.com

Cordiali saluti

Luca Benni

Luca Antignano said...

Ciao Nicola, ho bisogno di conferire con te per un problema legato ad un dump di una cartuccia CreatiVision, unica superstite tra le diagnostiche della Zanussi.
So che la cosa non ti riguarda direttamente, ma per la prima volta mi trovo in seria difficolta' col dump, e probabilmente la EPROM s'e' danneggiata.
Vorrei un tuo aiuto per estrarne il contenuto, magari con tecniche di decapping o simile... so che sei un esperto in questo senso.
Ti prego di contattarmi quanto prima. Ti ho mandato una mail qualche giorno fa, senza ricevere rsiposta. Ho anche contattato The Guru, ma non mi ha risposto nemmeno lui.
Saluti!
Luca "MADrigal" Antignano

satoma said...

Dear Nicola,

Whould you please contact me about some questions between new device & MAME.
This is a Inquiry regarding licensing of vital important.
I really need you reply.
Please mail to
gmrs951@hotmail.com

Looking forward to hearing from you soon

Best regards.

Supervisor said...

Hello Nicola!

1. Why in Super Street Fighter 2: The New Challenger sounds and music are playing very badly? An emulator Final Burn Alpha 0,2,5,0 (31.01.2003) is playing sounds and music very well. Laters versions of FBA and Mame are not playing good. Why?
2. Why there is no 3D Virtual Audio Qsound System? Qsound system archers is not fully emulated. Why? And Will be emulated in a near future? Are you played this game on true arcade board? I played and I remeber sounds and music and i must say what I hear on mame it is a some big mistake. I'm sad. Sounds and music in previously versions of Street Fighter are much better than in a newest version. But all other games on cps2 are melated with sounds and music very well. It is avery strengte. Don't you see?
3. Glitches on Cammy and Dee Jay stage. These glithes are not especially problem.

I'm not attacking you. I wan't some explanations. Are you and your project under Capcom control?

Best regards for you and your work.

Sorry for my english

mehmet99999 said...

producing a great emulator for sharing with us, thank you very much.

CPS2 system, second and third games of the final fight, you will add the emulator?

I'm talking about games: Final Fight 2 and Final Fight 3 [ CAPCOM (Not SNES)]

mehmetakin9999@hotmail.com

mancinii said...

Sorry if I did not put this post in the right place

I do not have anyone to turn to fix the emulation of a game (Space Battle Galactica-taito-Brazil) that belonged to a time of great happiness in my life.

I have the original hardware boards (it's all right about the sounds too, minus the noise of snoring takeoff of aircraft)

watch the video: http://www.youtube.com/watch?v=z60ewMRyqSs

MAME with the driver of an Indian Battle recognize sound (noise of aircraft taking off) when the galactica is played by him, and I do not know 'cause the original hardware fails (perhaps lacking a link to this and I do not know how)

Listen:
http://www.4shared.com/mp3/8hQFcGhX/aircraft_takeoff.html

This hardware also runs the game INDIAN BATTLE (http://www.youtube.com/watch?v=CQznDYAW37E)

The driver (MAME) INDIAN BATTLE NORMALLY works Galactica space battle

The crucial difference is that the Indian driver This battle can emulate the sound of snoring aircraft (DRIVER IN Galactica OFFICER CAN NOT MAME)

Let me explain: The Galactica's official driver in MAME plays all sounds except the sound of takeoffs of aircraft, see and hear:

http://www.youtube.com/watch?v=y8n_zimHj5g

The roar of planes appears when the game is played with the DRIVER OF INDIAN BATTLE, right?

I do the following: I put the roms Galactica with the same names of the Indian driver and play the game NORMALLY (but only with the sound of the roar of AIRCRAFT) ..

The difference is that the sound produced when playing this driver and the sound it generates is only the roar of planes and not heard NOTHING MORE!

So I concluded that the sound is that of the Indian MUSIC BECAUSE batle when playing the Indian battle (note: without the SAMPLES folder), the only sound that is generated is just the background music, and the same goes for when playing galactica the SOM that is generated is just the snoring AIRCRAFT!

http://www.youtube.com/watch?v=MOqjZKGnxsE&feature=related


This above video is played with the samples folder (not the folder that appears the only sound is the background music)


This video below is the DRIVER OF THE GAME BOWLING MAME THAT BELONGS TO INDIAN BATTLE (note: the folder with samples without the directory only if the snoring HEAR OF AIRCRAFT)!

(Http://www.youtube.com/watch?v=F89DjyJ68Vw)
Absolute certainty: The background music produced by the Indian battle game emulated by Grandmaster DERRICK Renauld, resolves the issue:

http://caesar.logiqx.com/php/mameinfo.php?id=indianbt

Let me explain: The correlation FUND OF INDIAN MUSIC BATTLE = is the production of the aircraft snoring.

WHY 2 games when played by this driver (Indian battle), only plays a sound (without the samples folder), ie, when the Indian is played, is heard only the music is played for fundo.Quando galactica, is heard only the snoring of the aircraft.

So .. The key question is how Derrick has done to the music of the Indian battle (one that says, .. 1,2,3 little Indians ..) has been emulated and deploys it on the driver's official GALACTICA


If you know how to contact him I thank

THANK YOU