https://crocs.fi.muni.cz @CRoCS_MUNI
PV204 Security technologies
JavaCard optimizations, Secure Multiparty Computation
Petr Švenda svenda@fi.muni.cz @rngsec
Centre for Research on Cryptography and Security, Masaryk University
(part of MPC slides done by Antonín Dufka)
Please comment on slides with anything unclear, incorrect or suggestions for improvement
https://drive.google.com/file/d/1vj_FtJG97gixLgQYuBR2NDNvg2LRMdro/view?usp=sharing
https://crocs.fi.muni.cz @CRoCS_MUNI
BEST PRACTICES (FOR APPLET
DEVELOPERS)
PV204 | Secure Multiparty Computation2
https://crocs.fi.muni.cz @CRoCS_MUNI
Quiz
1. Expect that your device is leaking in time/power channel.
Which option will you use?
– AES from hw coprocessor or software re-implementation?
– Short-term sensitive data stored in EEPROM or RAM?
– Persistent sensitive data in EEPROM or encrypted object?
– Conditional jumps on sensitive value?
2. Expect that attacker can successfully induct faults (random
change of bit(s) in device memory).
– Suggest defensive options for applet’s source code
– Change in RAM, EEPROM, instruction pointer, CPU flags…
3 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Security hints (1)
• Use algorithms/modes from JC API rather than your own implementation
– JC API algorithms fast and protected in cryptographic hardware
– general-purpose processor leaks more information (side-channels)
• Store session data in RAM
– faster and more secure against power analysis
– EEPROM has limited number of rewrites (10^5 – 10^6 writes)
• Never store keys, PINs or sensitive data in primitive arrays
– use specialized objects like OwnerPIN and Key
– better protected against power, fault and memory read-out attacks
– If not possible, generate random key in Key object, encrypt large data with this key and store only
encrypted data
• Make checksum on stored sensitive data (=> detect faults)
– check during applet selection (do not continue if data are corrupted)
– possibly check also before sensitive operation with the data (but performance penalty)
4 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Security hints (2)
• Erase unused keys and sensitive arrays
– use specialized method if exists (Key.clearKey())
– or overwrite with random data (Random.generate())
– Perform always before and after start of new session (new select, new device…)
• Use transactions to ensure atomic operations
– power supply can be interrupted inside code execution
– be aware of attacks by interrupted transactions - rollback attack
• Do not use conditional jumps with sensitive data
– branching after condition is recognizable with power analysis => timing/power
leakage
PV204 | Secure Multiparty Computation5
https://crocs.fi.muni.cz @CRoCS_MUNI
Security hints (3)
• Allocate all necessary resources in constructor
– applet installation usually in trusted environment
– prevents attacks based on limited available resources later during applet use
• Don’t use static attributes (except constants)
– Static attribute is shared between multiple instances of applet (bypasses applet firewall)
– Static pointer to array/engine filled by dynamic allocation cannot be removed until package
is removed from card (memory “leak”)
• Use automata-based programming model
– well defined states (e.g., user PIN verified)
– well defined transitions and allowed method calls
PV204 | Secure Multiparty Computation6
https://crocs.fi.muni.cz @CRoCS_MUNI
Security hints (4)
• Treat exceptions properly
– Do not let uncaught native exceptions to propagate away from the card
• 0x6f00 emitted – unclear what caused it from the terminal side
• Your applet is unaware of the exception (fault induction attack in progress?)
– Do not let your code to cause basic exceptions like OutOfBoundsException or
NullPointerExceptions…
• Slow handling of exceptions in general
• Code shall not depend on triggering lower-layer defense (like memory
protection)
7 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Security hints: fault induction (1)
• Cryptographic algorithms are sensitive to fault induction
– Single signature with fault from RSA-CRT may leak the private key
– Perform operation twice and compare results
– Perform reverse operation and compare (e.g., verify after sign)
• Use constants with large hamming distance
– Induced fault in variable will likely cause unknown value
– Use 0xA5 and 0x5A instead of 0 and 1 (correspondingly for more)
– Don’t use values 0x00 and 0xff (easier to force all bits to 0 or 1)
• Check that all sub-functions were executed [Fault.Flow]
– Fault may force program stack or stack to skip some code
– Idea: Add defined value to flow counter inside target sub-function, check later for expected
sum. Add also in branches.
8 PV204 | Secure Multiparty Computation
Secure Application Programming in the presence of Side Channel Attacks, Riscure
https://crocs.fi.muni.cz @CRoCS_MUNI
Security hints: fault induction (2)
• Replace single condition check by complementary check
– conditionalValue is sensitive value
– Do not use boolean values for sensitive decisions
• Verify number of actually performed loop iterations
PV204 | Secure Multiparty Computation9
Secure Application Programming in the presence of Side Channel Attacks, Riscure
if (conditionalValue == 0x3CA5965A) { // enter critical path
// . . .
if (~conditionalValue != 0xC35A69A5) {
faultDetect(); // fail if complement not equal to 0xC35A69A5
}
// . . .
}
int i;
for ( i = 0; i < n; i++ ) { // important loop that must be completed
//. . .
}
if (i != n) { // loop not completed
faultDetect();
}
https://crocs.fi.muni.cz @CRoCS_MUNI
Security hints: fault induction (3)
• Insert random delays around sensitive operations
– Randomization makes targeted faults more difficult
– for loop with random number of iterations (for every run)
• Monitor and respond to detected induced faults
– If fault is detected (using previous methods), increase fault counter.
– Erase keys / lock card after reaching some threshold (~10)
• Natural causes may occasionally cause fault => > 1
10 PV204 | Secure Multiparty Computation
Secure Application Programming in the presence of Side Channel Attacks, Riscure
https://crocs.fi.muni.cz @CRoCS_MUNI
How and when to apply protections
11 PV204 | Secure Multiparty Computation
Riscure
More in PV286:
“Programming in the presence
of side-channels / faults"
https://crocs.fi.muni.cz @CRoCS_MUNI
Execution speed hints (1)
• Big difference between RAM and EEPROM memory
– new allocates in EEPROM (persistent, but slow)
• do not use EEPROM for temporary data
• do not use for sensitive data (keys)
– JCSystem.getTransientByteArray() for RAM buffer
– local variables automatically in RAM
• Use algorithms from JavaCard API and utility methods
– much faster, cryptographic co-processor
• Allocate all necessary resources in constructor
– executed during installation (only once)
– either you get everything you want or not install at all
PV204 | Secure Multiparty Computation12
https://crocs.fi.muni.cz @CRoCS_MUNI
Execution speed hints (2)
• Garbage collection limited or not available
– do not use new except in constructor
• Use copy-free style of methods
– foo(byte[] buffer, short start_offset, short length)
• Do not use recursion or frequent function calls
– slow, function context overhead
• Do not use OO design extensively (slow)
• Keep Cipher or Signature objects initialized
– if possible (e.g., fixed master key for subsequent derivation)
– initialization with key takes non-trivial time
PV204 | Secure Multiparty Computation13
https://crocs.fi.muni.cz @CRoCS_MUNI
JCPROFILERNEXT – PERFORMANCE
PROFILING, NON-CONSTANT TIME
DETECTION
14 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
JCProfilerNext: on-card performance profiler
• Open-source on-card performance profiler (L. Zaoral)
– https://github.com/lzaoral/JCProfilerNext
• Automatically instrumentation of provided JavaCard code
– Conditional exception emitted on defined line of code
– Spoon tool used https://spoon.gforge.inria.fr/
• Measures time to reach specific line (measured on client-side)
• Fully automatic, no need for special setup (only JavaCard + reader)
• Goals:
– Help developer to identify parts for performance optimizations
– Help to detect (significant) timing leakages
– Insert “triggers” visible on side-channel analysis
– Insert conditional breakpoints…
15 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Instrumented code (Spoon)
16
private void example(APDU apdu) {
short count = Util.getShort(apdu.getBuffer(), ISO7816.OFFSET_CDATA);
for (short i = 0; i < count; i++) {
short tmp = 0;
for (short k = 0; k < 50; k++) {
tmp++;
}
}
}
PM.check(PMC.TRAP_example_Example_example_argb_javacard_framework_APDU_arge_1);
PM.check(PMC.TRAP_example_Example_example_argb_javacard_framework_APDU_arge_2);
PM.check(PMC.TRAP_example_Example_example_argb_javacard_framework_APDU_arge_3);
PM.check(PMC.TRAP_example_Example_example_argb_javacard_framework_APDU_arge_4);
PM.check(PMC.TRAP_example_Example_example_argb_javacard_framework_APDU_arge_5);
PM.check(PMC.TRAP_example_Example_example_argb_javacard_framework_APDU_arge_6);
PM.check(PMC.TRAP_example_Example_example_argb_javacard_framework_APDU_arge_7);
PM.check(PMC.TRAP_example_Example_example_argb_javacard_framework_APDU_arge_8);
// if m_perfStop equals to stopCondition, exception is thrown (trap hit)
public static void check(short stopCondition) {
if (PM.m_perfStop == stopCondition) {
ISOException.throwIt(stopCondition);
}
}
https://crocs.fi.muni.cz @CRoCS_MUNI
JCProfilerNext – timing profile of target line of code
17 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
JCProfilerNext – memory consumption
18 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Checking for non-constant time execution
19 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNIPV204 | Secure Multiparty Computation
JavaCard applet firewall issues
• Main defense for separation of multiple applets
• Platform implementations differ
– Usually due to the unclear and complex specification
• If problem exists, then is out of developer’s control
• Firewall Tester project (W. Mostowski)
– Open and free, the goal is to test the platform
– http://www.sos.cs.ru.nl/applications/smartcards/firewalltester/
short[] array1, array2; // persistent variables
short[] localArray = null; // local array
JCSystem.beginTransaction();
array1 = new short[1];
array2 = localArray = array1; // dangling reference!
JCSystem.abortTransaction();
20
https://crocs.fi.muni.cz @CRoCS_MUNI
Relevant open-source projects
• Easy building of applets
– https://github.com/martinpaljak/ant-javacard
– https://github.com/ph4r05/javacard-gradle-template
• AppletPlayground (ready to “fiddle” with applets)
– https://github.com/martinpaljak/AppletPlayground
• Card simulator https://jcardsim.org
• Profiling performance
– https://github.com/crocs-muni/JCAlgTest
– https://github.com/lzaoral/JCProfilerNext
• Curated list of JavaCard applets
– https://github.com/crocs-muni/javacard-curated-list
• Low-level ECPoint library
– https://github.com/OpenCryptoProject/JCMathLib
21 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI22 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
SECURE MULTIPARTY COMPUTATION
23 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
SECURE MULTIPARTY COMPUTATION
(TO REMOVE SINGLE POINT OF FAILURE)
24 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Possibly heard of ROCA vulnerability CVE-2017-15361
25 PV204 | Secure Multiparty Computation
https://roca.crocs.fi.muni.cz
Austria, Estonia,
Slovakia, Spain…
25-30% TPMs worldwide,
BitLocker, ChromeOS…
Firmware update available
Commit signing,
Application signing
GitHub, Maven…
Gemalto .NET
Yubikey 4…
Yubikey 4…
Very few keys, but all tied
to SCADA management
Single point of failure:
Prime generation of RSA
keygen in widely used
chip (1-2 billion chips)
https://crocs.fi.muni.cz @CRoCS_MUNI
Single point of failure
• We already try to avoid single point of failure at many places
– Personal: dual control, people from different backgrounds…
– Technical: Load-balancing web servers, RAID, periodic backups…
– Supply chain: no reliance on single supplier…
• Problems: Appropriate trade-off between security, cost and usability
• Systems without single point of failure tend to be:
– More complex
– More expensive
– Less performant
– Backward incompatible
– (not really without single point of failure)
PV204 | Secure Multiparty Computation
zerodayclothing.com
26
https://crocs.fi.muni.cz @CRoCS_MUNI
REMOVING SINGLE POINT OF FAILURE
IN CRYPTOGRAPHIC SIGNATURES
27 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Single signature
28 PV204 | Secure Multiparty Computation
Signature Signature SignatureSignature
Multiple signatures
MPC signature
Signature
Analogically for decryption
(single person decrypts,
multiple people, k-of-n)
Shamir TSS
Share 3
Share 2
Share 1
https://crocs.fi.muni.cz @CRoCS_MUNI
Option: Cryptographic “garden”
• Electronic signature == sign_RSA(SHA256(message))
– Failure in RSA or SHA256 algorithm or its implementation => forgery of
signatures
• Signature using cryptographic “garden”
– Differently computed (algorithm) signatures over same message
– Signature = sign_RSA+ sign_ECC + sign_PostQuantumAlg
– Mitigate design problems of particular algorithm
• Disadvantages: backward (in-)compatibility, larger storage space…
PV204 | Secure Multiparty Computation
Signature
ECC PQC
Signature
RSA
RSA
29
https://crocs.fi.muni.cz @CRoCS_MUNI
Secure Multi-Party Computation
• “Offload heavy computation to untrusted party while not leaking info”
• “Distribute critical cryptographic operation among N parties”
30 PV204 | Secure Multiparty Computation
Example:
• Amazon evaluates trained neural network on medical image (on behalf of user)
• Amazon learns neither the trained NN, nor the processed image
• Technology: Homomorphic encryption, garbled circuits (slow, but getting better)
Example:
• 3 devices collaboratively compute digital ECC signature
• Private key never at single place, secure unless all devices are compromised
• Technology: purpose tailored schemes (efficient, provably secure)
Focusofthislecture
https://crocs.fi.muni.cz @CRoCS_MUNI
Threshold cryptography
• Proposed already in 1987 by Y. Desmedt
• Principle
– Private key split into multiple parts (“shares”)
– Shares used (independently) by separate parties during a protocol to perform
desired cryptographic operation
– If enough shares are available, operation is finished successfully
• Properties
– Better protection of private key (single point of failure removed)
– Key shares can be distributed to multiple parties (independent usage condition)
– Resulting signature may be indistinguishable from a standard one (e.g., ECDSA)
• Significant research progress made in the cryptocurrency context
31
PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Threshold cryptography protocols
• Typically, distributed key generation is also included
– Private key is not generated on a single device
• Output signatures can be indistinguishable from single party signatures
– ECDSA ([GGN16], [LN18], [GG18], [GG20], [Can+20], …)
– Schnorr (MuSig, MuSig2, FROST…)
– RSA ([DF91], [Gen+97], [DK01], Smart-ID…)
• Various designs with different properties
– Supported setups (n-of-n / t-of-n)
– Number of communication rounds
– Computation complexity
– Security assumptions…
https://crocs.fi.muni.cz @CRoCS_MUNI
PRACTICAL EXAMPLES OF MPC
33 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Smart-ID signature system
• Banks in Baltic states, >4M users
– Qualified Signature Creation Device (QSCD)!
• Collaborative computation of signature using:
1. User’s mobile device (3072b RSA)
2. Smart-ID service provider (3072b RSA)
• Two-party RSA signatures, threshold signature scheme
– Whole signature key never present at a single place
– Smart-ID service provider cannot alone compute valid signature
• Final signature is 6144b RSA => compatible with existing systems
– Assumed security level is equivalent to 3072b RSA (as if one party compromised)
PV204 | Secure Multiparty Computation
6k RSA
Signature
Sign 3k RSA Sign 3k RSA
34
https://crocs.fi.muni.cz @CRoCS_MUNI
MPC wallets (software, hardware)
• Number of cryptocurrencies uses ECDSA/EdDSA/Schnorr algorithm to authorize TX
– Funds are lost if private key is stolen/lost
• Multiple separate signatures by separate private keys possible (so called multisignature)
– More costly (more onchain space => higher fee)
– Privacy leaking (structure of approval)
– Not always (directly) supported (Bitcoin has IP_CHECKMULTISIG, Ethereum needs special contract)
• MPC to compute threshold multiparty signature
– Interaction between multiple entities, single signature as a result
– Not recognizable from standard transactions on-chain
• ECDSA
– Several end-user wallets like ZenGo, Binance, Coinbase… as well as institutional custodians
– Usually one share by user, second by server
• Schnorr-based signatures easier to compute (e.g., Musig-2, FROST)
– Available in Bitcoin after Taproot
35 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
True2F FIDO U2F token
• Yubikey 4 has single master key
– To efficiently derive keypairs for separate Relying parties (Google, GitHub…)
– Inserted during manufacturing phase (what if compromised?)
• Additional SMPC protocols (as protection against backdoored token)
– Verifiable insertion of browser randomness into final keypairs
– Prevention of private key leakage via ECDSA padding
• Backward-compatible (Relying party, HW)
• Efficient: 57ms vs. 23ms to authenticate
36 PV204 | Secure Multiparty Computation
https://arxiv.org/pdf/1810.04660.pdf
https://crocs.fi.muni.cz @CRoCS_MUNI
Cryptography as a Service (CaaS)
WS API: JSON
Hardware Security
Module (HSM)
PV204 | Secure Multiparty Computation37
• CaaS creates single point of
failure (SPoF)
– More risk to server
• Typically solved by HSM
• HSM becomes SPoF!
https://crocs.fi.muni.cz @CRoCS_MUNI38 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz/papers/space2015
First prototype:
12+2 configuration
1U prototype:
43+2 configuration
Dedicated board:
110+10 cards configuration
Performance:
~600 RSA-1024 signs/sec
~1200 HMAC/sec
CryptoHive
https://crocs.fi.muni.cz @CRoCS_MUNI
Problem: buggy or subverted chip
39 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz/papers/mpc_ccs17
https://crocs.fi.muni.cz/papers/mpc_ccs17
• Prevention of supply chain compromise or buggy chip
• Suite of ECC-based multi-party protocols proposed
– Distributed key generation, ElGamal decryption, Schnorr signing
• Efficient implementation on JavaCards + high-speed box
• Combination with non-smartcard devices possible
https://crocs.fi.muni.cz @CRoCS_MUNI
SmartHSM for multiparty (120 smartcards, 3 cards/quorum)
PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz/papers/mpc_ccs17
…
120 cards => 40 quorums
=> 300+ decrypt / second
=> 80+ signatures / second
40
https://crocs.fi.muni.cz @CRoCS_MUNI
How to run MPC on JavaCards
• Myst MPC applet: https://github.com/OpenCryptoProject/Myst
• Schnorr-based MPC protocols requires low-level curve operations
– Supported by card, but not exposed by standard JavaCard API
• JCMathLib https://github.com/OpenCryptoProject/JCMathLib
– Adds support for low-level classes/methods like ECPoint and Integer
• Which are otherwise not supported by public JavaCard API
• (available via proprietary extensions, but requires NDA)
– Main goals
1. Expose helpful functions for research/FOSS usage (e.g., Schnorr MPC sigs)
2. Allow for publication of functional applets originally based on proprietary API
– Low-level methods build (mis)using existing JC API
• E.g., ECPoint.multiply() using ECDH KeyAgreement + additional computation
– Optimized for low RAM memory footprint and performance
41 PV204 | Secure Multiparty Computation
https://github.com/OpenCryptoProject/JCMathLib
https://crocs.fi.muni.cz @CRoCS_MUNI
SHINE: Interoperability of MPC signatures
• Idea: make existing Schnorr-based MPC protocols interoperable via
untrusted mediator
– NE-based schemes (CoSi, Myst)
– NC-based schemes (MuSig, MSDL)
– Half-ND-based schemes (MuSig2, SpeedyMuSig)
• Additional multi-signature protocol optimized for smartcards (SHINE)
– JCMathLib used
SHINE: Resilience via Practical Interoperability of Multi-party Schnorr Signature Schemes,
Antonin Dufka, Vladimir Sedlacek, Petr Svenda, SECRYPT , 2022.
PV204 | Secure Multiparty Computation42
https://crocs.fi.muni.cz @CRoCS_MUNI
MeeSign (k-of-n ECDSA)
• Platform for multi-party document signing
– MPC utilized for group signing and backward compatibility
– Outputs valid PDF signatures by multiple parties
MeeSign: Threshold signing for electronic evidence management. Antonin Dufka, Jakub Janku, Jiri Gavenda,
Petr Svenda. EurOpen 2022. Also available on https://meesign.crocs.fi.muni.cz/.
PV204 | Secure Multiparty Computation43
https://crocs.fi.muni.cz @CRoCS_MUNI44 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
USE-CASE SCENARIOS
45 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
High-level usage scenarios
1. Digital signature
2. User authentication
3. Data decryption
4. Key / randomness generation
46 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Multiparty signatures – configurations and use-cases
• 2-out-of-2 (two signers, both required)
– One share on mobile phone, second on server (Smart-ID, eIDAS compliant)
– One share on US smartcard, second on Chinese smartcard (backdoor resistance)
• 2-out-of-3 (three signers total, at least two required)
– Two shares user, one share backup server (backup if user lose one share)
– One share lender, one share lendee, one share arbiter (for disputes)
• 1-out-of-3 (very robust backup against key loss)
• 3-out-of-5 (shares distribution voting)
– CEO has 2 shares, all other have only single one
• 11-out-of-15 (Liquid consortium signing blocks on Liquid sidechain)
47 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Multiparty signatures with additional policy
• Signers can also enforce specific signing policy
– Only during certain time, documents, type of operations, certain amount…
• 2-out-of-2 with policy
– One person, second automatic signer only during office hours
• 2-out-of-3 with policy (two people, one automated device with policy)
– Two people together can always sign/transfer, one person alone only up to limit)
• 3-out-of-3 (two people, one automated device with policy)
– Automated device signs only when previous two already signed and additionally
impose 1-month delay (timelock)
48 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
MPC for authentication – configurations
• 2-of-2: one user, two devices
– (higher security against device compromise)
• 2-of-2: one user, one server-side automatic process
– (check time interval when authentication is allowed)
• 2-of-2: two users (user, approving controller)
– (access must be approved by controller)
• 2-of-3: three users (user, redundant approvers)
– (one user, two controllers – one approval is enough)
• Bonus: Independent log of authentication attempt
49 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Multiparty decryption and Shamir threshold scheme
• Combination of MPC and Shamir
– 2-of-2 multiparty decryption for every person to decrypt Shamir share
– Shamir shares combined later (standard procedure)
– Usable to enable easy removal of person from share (by deletion of second key
for 2-of-2)
50 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Threshold crypto protocols – tradeoffs and limitations
• Security vs. usability
• More difficult to finalize signature (more parties)
• More complex software (bugs)
• Number of rounds
• Amount of data exchanged
• Active research field => possibility for new attacks against whole
schemes
51 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Summary
• JavaCard programming
– Optimizations need to consider underlaying hardware (RAM, co-processors…)
– Programs shall anticipate faults during computation (injected by an attacker)
• Secure Multiparty Computation
– Exciting domain, active research, many practical uses
– Collaborative computation of signatures, decryption, keygen…
– Can be backward compatible (k-ECDSA, k-RSA, k-Schnorr…)
– Usually more computational demanding (common CPU is enough)
– Some protocols efficient enough to run on smartcards (Schnorr-based sigs…)
• Split to multiple parties provides:
– Better protection of private key against bugs and compromise
– Possibility of additional policy before party participation
52 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI53 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Additional slides for generic multiparty computation and
whitebox cryptography construction (for interested, not
mandatory part of PV204 course)
54 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Secure Multiparty Computation (MPC)
• Enables multiple parties to jointly compute a function, but keeps their inputs private
• Different types of protocols:
• Secret sharing protocols (e.g., Shamir)
– Jointly hold secret, but split in shares, can be reconstructed only when sufficient number of shares are
available
• Garbled circuit protocol
– One party creates Boolean circuit (2-input gates) from the specification and transforms it (XOR, AND)
– Other party evaluates without learning original specification and/or data
• Partial/Somewhat/Fully Homomorphic Encryption (PHE, SHE, FHE)
• Oblivious Transfer, Secure Function Evaluation
55 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
HOW TO PROTECT
Protections Against Reverse Engineering
PV204 | Secure Multiparty Computation56
https://crocs.fi.muni.cz @CRoCS_MUNI
Standard vs. whitebox attacker model
(symmetric crypto example)
PV204 | Secure Multiparty Computation57
https://crocs.fi.muni.cz @CRoCS_MUNI
Whitebox attacker model
• The attacker is able to:
– inspect and disassemble binary (static strings, code...)
– observe/modify all executed instructions (OllyDbg...)
– observe/modify used memory (OllyDbg, memory dump...)
• How to still protect value of cryptographic key?
• Who might be whitebox attacker?
– Mathematician (for fun)
– Security researcher / Malware analyst (for work)
– DRM cracker (for fun&profit)
– ...
PV204 | Secure Multiparty Computation58
https://crocs.fi.muni.cz @CRoCS_MUNI
Classical obfuscation and its limits
• Provides only time-limited protection
• Obfuscation is mostly based on obscurity
– add bogus jumps
– reorder related memory blocks
– transform code into equivalent one, but less readable
– pack binary into randomized virtual machine...
• Barak’s (im)possibility result (2001)
– family of functions that will always leak some information
– but practical implementation may exist for others
• Cannetti et. al. positive results for point functions
• Goldwasser et. al. negative result for auxiliary inputs
PV204 | Secure Multiparty Computation59
https://crocs.fi.muni.cz @CRoCS_MUNI
CEF&CED
Computation with Encrypted Data and Encrypted Function
PV204 | Secure Multiparty Computation60
https://crocs.fi.muni.cz @CRoCS_MUNI
Scenario
• We’d like to compute function F over data D
– secret algorithm F or sensitive data D (or both)
• Solution with trusted environment
– my trusted PC, trusted server, trusted cloud…
• Problem: can be cloud or client really trusted?
– server hack, DRM, malware...
• Whitebox attacker model
– controls execution environment (debugging)
– sees all instructions and data executed
PV204 | Secure Multiparty Computation61
https://crocs.fi.muni.cz @CRoCS_MUNI
CEF
• Computation with Encrypted Function (CEF)
– A provides function F in form of P(F)
– P(F) can be executed on B’s machine with B’s data D
– B will not learn function F during its computation (except Di to F(Di) mapping)
62 PV204 | Secure Multiparty Computation
A B
https://crocs.fi.muni.cz @CRoCS_MUNI
CED
• Computation with Encrypted Data (CED)
– B provides encrypted data D as E(D) to A
– A is able to compute its F as F(E(D)) to produce E(F(D))
• result of F over D, but encrypted
– A will not learn data D
– E(F(D)) is returned back to B and decrypted
63 PV204 | Secure Multiparty Computation
A B
https://crocs.fi.muni.cz @CRoCS_MUNI
CED via homomorphism
1. Convert your function into Boolean circuit with additions (xor) and
multiplications (and)
2. Compute addition and/or multiplication “securely”
– an attacker can compute E(D1+D2) = E(D1)+E(D2)
– but can learn neither D1 nor D2
3. Execute whole circuit over encrypted data
PV204 | Secure Multiparty Computation64
https://crocs.fi.muni.cz @CRoCS_MUNI
Types of homomorphic schemes
• Partial homomorphic scheme
– either addition or multiplication is possible, but not both; any number of times
• Somewhat homomorphic scheme
– Both operations possible, but only limited number of times
• Fully homomorphic scheme
– both addition and multiplication; unlimited number of times (any computable function)
PV204 | Secure Multiparty Computation65
https://crocs.fi.muni.cz @CRoCS_MUNI
Partial homomorphic schemes
• Example with RSA (multiplication)
– E(d1).E(d2) = d1
e . d2
e mod m = (d1d2)e mod m = E(d1d2)
• Example Goldwasser-Micali (addition)
– E(d1).E(d2) = xd1r1
2 . Xd2r2
2 = xd1+d2(r1r2)2 = E(d1d2)
• Limited to polynomial and rational functions
• Limited to only one type of operation (mult or add)
– or one type and very limited number of other type
• Slow – based on modular mult or exponentiation
– every operation equivalent to whole RSA operation
PV204 | Secure Multiparty Computation66
https://crocs.fi.muni.cz @CRoCS_MUNI
Somewhat Homomorphic Encryption
• Both operations (mult and add) possible, but only limited number of
times
• BGV (Barrat, Gentry and Vaikuntanathan) scheme
• GSW (Gentry-Sahai-Waters) scheme
67 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Fully homomorphic scheme (FHE)
• Holy grail - idea proposed in 1978 (Rivest et al.)
– both addition and multiplication securely
• But no scheme until 2009 (Gentry)!
• Fully homomorphic encryption
– based on lattices over integers
– noisy somewhat homomorphic encryption usable only for few operations
– combined with repair operation (enable to use it for more operations again)
68 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
Fully homomorphic scheme - usages
• Outsourced cloud computing and storage
– FHE search, Private Database Queries
– protection of the query content
• Secure voting protocols
– yes/no vote, resulting decision
• Protection of proprietary info - MRI machines
– expensive algorithm analyzing MR data, HW protected
– central processing restricted due to private patient’s data
• …
PV204 | Secure Multiparty Computation69
https://crocs.fi.muni.cz @CRoCS_MUNI
Fully homomorphic scheme - practicality
• Not very practical (yet ☺) (Gentry, 2009)
– 2.7GB key & 2h computation for every repair operation
– repair needed every ~10 multiplication
• FHE-AES implementation (Gentry, 2012)
– standard PC  37 minutes/block (but 256GB RAM)
• Gentry-Halevi FHE accelerated in HW (2014)
– GPU / ASICS, many blocks in parallel => 5 minutes/block
• Replacing AES with other cipher (Simon) (2014)
– 2 seconds/block
• Very active research area!
PV204 | Secure Multiparty Computation70
https://crocs.fi.muni.cz @CRoCS_MUNI
Partial/Fully Homomorphic Encryption libraries
• Homomorphic encryption libraries: HElib, FV-NFLlib, SEAL
• Comparison of features and performance
– https://arxiv.org/pdf/1812.02428v1.pdf
– https://link.springer.com/chapter/10.1007/978-3-030-12942-2_32
71 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
WHITEBOX CRYPTOGRAPHY
72 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
White-box attack resistant cryptography
• How to protect symmetric cryptography cipher?
– protects used cryptographic key (and data)
• Special implementation fully compatible with standard AES/DES…
2002 (Chow et al.)
– series of lookups into pre-computed tables
• Implementation of AES which takes only data
– key is already embedded inside
– hard for an attacker to extract embedded key
– Distinction between key and implementation of algorithm (AES) is removed
PV204 | Secure Multiparty Computation73
https://crocs.fi.muni.cz @CRoCS_MUNIPV204 | Secure Multiparty Computation
Whitebox transform
74
https://crocs.fi.muni.cz @CRoCS_MUNI
Impractical solution
• Secure, but 2128 x 16B memory storage
PV204 | Secure Multiparty Computation
00…00…00
00…00…01
00…01…11
11…11…11
01…11…11
…
…
10…01…11
10…11…01
01…11…11
10…00…10
01…10…00
…
…
2128
Input block Output block = AES(input, keyX)
Precomputed table
usedasindexintotable
2128
75
https://crocs.fi.muni.cz @CRoCS_MUNI
WBACR AES – some techniques
• Pre-compute table for all possible inputs
– practical for one 16bits or two 8bits arguments table with up to 216 rows
(~64KB)
– AddRoundKey: data  key
• 8bit argument data, key fixed
• Pack several operations together
– AddRoundKey+SubBytes: T[i] = S[i  key];
• Protect intermediate values by random bijections
– removed automatically by next lookup
– X = F-1(F(X))
– T[i] = S[F-1(i)  key];
PV204 | Secure Multiparty Computation76
https://crocs.fi.muni.cz @CRoCS_MUNI
AES – short remainder (used ops)
PV204 | Secure Multiparty Computation
Pictures taken from http://en.wikipedia.org/wiki/Advanced_Encryption_Standard
77
https://crocs.fi.muni.cz @CRoCS_MUNIPV204 | Secure Multiparty Computation78
https://crocs.fi.muni.cz @CRoCS_MUNI
Whitebox cryptography lifecycle
• [Secure environment]
1. Generate required key (random, database...)
2. Generate WAES tables (in secure environment)
• [Potential insecure environment]
3. Compile WAES tables into target application
• [Insecure environment (User PC)]
4. Run application and use WAES as usual (with fixed key)
PV204 | Secure Multiparty Computation79
https://crocs.fi.muni.cz @CRoCS_MUNIPV204 | Secure Multiparty Computation
makeTable()
precompTable
data encrypted data
encrypt(data)
AES key
Environment under control
of an attacker
Environment outside control
of an attacker
80
https://crocs.fi.muni.cz @CRoCS_MUNI
Resulting implementation
• More difficult to detect that crypto was used
– no fixed constants in the code
– precomputed tables change for every new AES instance
• even two tables for same key are different
– (but can still be detected)
• Resistant even when precomputed tables are found
– when debugged, only table lookups are seen
– key value is never manipulated in plaintext
– transformation techniques should provide protection to key embedded inside
tables
PV204 | Secure Multiparty Computation81
https://crocs.fi.muni.cz @CRoCS_MUNI
Demo – WAES
• WAES tables generator
– configuration options
– *.h files with pre-computed tables
• WAES cipher implementation
– compile-in tables
– tables as memory blob
PV204 | Secure Multiparty Computation82
https://crocs.fi.muni.cz @CRoCS_MUNI
WAES performance
• Intel Core i5 M560@2.67GHz
PV204 | Secure Multiparty Computation
L. Bacinska, https://is.muni.cz//th/373854/fi_m/
83
https://crocs.fi.muni.cz @CRoCS_MUNI
WBACR Ciphers - pros
• Practically usable (size/speed)
– implementation size ~800KB (WBACR AES tables)
– speed ~MBs/sec (WBACRAES ~6.5MB/s vs. 220MB/s)
• Hard to extract embedded key
– Complexity semi-formally guaranteed (if scheme is secure)
– AES shown unsuitable (all WBARC AESes are broken)
• One can simulate asymmetric cryptography!
– implementation contains only encryption part of cipher
– until attacker extracts key, decryption is not possible
84 PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz @CRoCS_MUNI
WBACR Ciphers - cons
• Implementation can be used as oracle (black box)
– attacker can supply inputs and obtain outputs
– even if she cannot extract the key
– (can be partially solved by I/O encodings)
• Problem of secure input/output
– protected is only cipher (e.g., AES), not code around
• Key is fixed and cannot be easily changed
• Successful cryptanalysis for several schemes 
– several former schemes broken
– new techniques being proposed
PV204 | Secure Multiparty Computation85
https://crocs.fi.muni.cz @CRoCS_MUNI
Space-Hard Ciphers
• Space-hard notion of WBACR ciphers
– How much can be fnc compressed after key extraction?
• WBACR AES=>16B key=>extreme compression (bad)
– Amount of code to extract to maintain functionality
• SPACE suite of space-hard ciphers
– Combination of l-line target heavy Feistel network and precomputed lookup
tables (e.g., by AES)
– Variable code size to exec time tradeoffs
PV204 | Secure Multiparty Computation86
https://crocs.fi.muni.cz @CRoCS_MUNI
Can whitebox transform replace secure hardware (e.g.,
smart card)?
• Only to limited extent
• Limitation of arguments size
• Operation atomicity
– one cannot execute only half of card’s operations
• No secure memory storage
– no secure update of state (counter)
• Both can be used as black-box
– smart card can use PIN to limit usage
• But still some reasonable usages remain
PV204 | Secure Multiparty Computation87
https://crocs.fi.muni.cz @CRoCS_MUNI
List of proposals and attacks
• (2002) First WB AES implementation by Chow et. al. [Chow02]
– IO bijections, linear mixing bijections, external coding
– broken by BGE cryptanalysis [Bill04]
• algebraic attack, recovering symmetric key by modelling round function by system of algebraic equations
• (2006) White Box Cryptography: A New Attempt [Bri06]
– attempt to randomize whitebox primitives, perturbation & random equations added, S-boxes are enc. keys. 4 AES ciphers, major
voting for result
– broken by Mulder et. al. [Mul10]
• removes perturbations and random equations, attacking on final round removing perturbations, structural decomposition. 217
steps
• (2009) A Secure Implementation of White-box AES [Xia09]
– broken by Mulder et. al. [Mul12]
• linear equivalence algorithm used (backward AES-128 compatibility => linear protection has to be inverted in next round), 232
steps
• (2011) Protecting white-box AES with dual ciphers [Kar11]
– broken by our work [Kli13]
• protection shown to be ineffective
• Fault induction especially devastating
PV204 | Secure Multiparty Computation88
https://crocs.fi.muni.cz @CRoCS_MUNI
BGE attack in progress
PV204 | Secure Multiparty Computation89
https://crocs.fi.muni.cz @CRoCS_MUNI
More resources
• Overviews, links
– http://whiteboxcrypto.com/research.php
– https://minotaur.fi.muni.cz:8443/~xsvenda/docuwiki/doku.php?id=public:mobi
lecrypto
• Crackme challenges
– http://www.phrack.org/issues.html?issue=68&id=8
• Whitebox crypto in DRM
– http://whiteboxcrypto.com/files/2012_MISC_DRM.pdf
PV204 | Secure Multiparty Computation90
https://crocs.fi.muni.cz @CRoCS_MUNI
Whitebox transform IS used in the wild
• Proprietary DRM systems
– details are usually not published
– AES-based functions, keyed hash functions, RSA, ECC...
– interconnection with surrounding code
• Chow at al. (2002) proposal made at Cloakware
– firmware protection solution
• Apple’s FairPlay & Brahms attack
• http://whiteboxcrypto.com/files/2012_MISC_DRM.pdf
• ...
PV204 | Secure Multiparty Computation91