There is an option that has not yet been mentioned in this thread: On the secure element that is used in the Nokia phones the MIFARE portion is accessible though JavaCard applets. The operating system of the JavaCard provides a special API (ExtSystem) that allows accessing the MIFARE area. (See the WIKI page "Applets in Java Card area can access the Mifare 4k area with G&D specific libraries (ExtSystem) provided by Sm@rtCafé® Professional Toolkit. ")
Therefore, you could create a JavaCard applet that handles the access to the MIFARE area. Thus, the MIFARE keys will never escape the secure JavaCard applet's environment. Still you would have to secure the access to the JavaCard applet. This could for instance be done with
- a PIN code that the user enters into the phone (Compared to the previously mentioned PIN code based generation of the MIFARE keys this variant has an important advantage: The PIN code can be verified by the JavaCard. Thus, restrictions on PIN code entry (like a limited number of retries) that are typically known from smartcards can be used.)
- the APDUs for accessing the JavaCard applet can be generated on a remote server. Therefore, an encrypted tunnel can be established between the JavaCard applet and the remote server. This would render attacks on the MIDlet (that only redirects encrypted APDUs) rather useless.
Yet, this approach does not account for security vulnerabilites through MIFARE Classic's broken cryptographic algorithms.
JavaCard applets are small java programs. They are executed in a secure and tamper proof environment that has all the advantages of classic multi-application processor smartcards. The applets are accessed (from an external reader as well as from the MIDlet) through APDU commands. You can implement quite complex programs that use cryptographic features/algorithms of the smartcard and store data in the tamper proof smartcard environment. But implementation of such an applet requires "advanced" programming skills.
In both cases you need a key to authenticate, but with the MIFARE API you have to handle the plain key in the MIDlet while the JavaCard approach provides other options like the ones I mentioned before.
For examples on JavaCard programming, you could take a look at the various samples that come with the JavaCard development kit. Also the Nokia 6131 SDK provides an example named "InternalSecureCardExample" that demonstrates how to access a JavaCard applet from Java ME.