P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\titulka.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\titulka.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\titulka.jpg
PV204 Security technologies
JavaCard optimizations, Secure Multiparty Computation and Trhreshold signatures
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/1DD5tgyaS8Nk_Wze97_IJpVBRQhXuwgT8/view?usp=drive_link

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
BEST PRACTICES (FOR APPLET DEVELOPERS)
•
PV204 | Secure Multiparty Computation
2

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
5

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
6

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
9
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();
}

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
How and when to apply protections
11
PV204 | Secure Multiparty Computation
Riscure

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
12

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
13

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
JCPROFILERNEXT – PERFORMANCE PROFILING, NON-CONSTANT TIME DETECTION
•
14
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Instrumented code (Spoon)
16
PV204 | Secure Multiparty Computation
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);
    }
}

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
JCProfilerNext – timing profile of target line of code
17
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
JCProfilerNext – memory consumption
•
18
PV204 | Secure Multiparty Computation
Graphical user interface, application Description automatically generated

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Chart Description automatically generated with medium confidence
Checking for non-constant time execution
19
PV204 | Secure Multiparty Computation
•

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
PV204 | 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

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
–
–
•
22
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
THRESHOLD CRYPTOGRAPHY
(TO REMOVE SINGLE POINT OF FAILURE)
•
23
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Possibly heard of ROCA vulnerability CVE-2017-15361
24
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)

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
25

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
REMOVING SINGLE POINT OF FAILURE IN CRYPTOGRAPHIC SIGNATURES
•
26
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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”
27
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)

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Goals of threshold cryptography
1.Remove single point of failure
–Reduce trust requirements (no single party can fail you)
–Better protect against attacks like malware (no single device with full key)
–Provide resiliency against subset compromise (k-of-n)
2.Provide fault tolerance (n-of-n vs. k-of-n)
–Perform operation with some parties not available
3.Enable different signing/decryption policies to be enforced (each party)
–Regulatory requirements (e.g., “four eyes principle”)
•
•
28
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Icon Description automatically generated Text, letter Description automatically generated
Single signature
29
PV204 | Secure Multiparty Computation
D:\Documents\Obrázky\is2\Phone-icon.png D:\Documents\Obrázky\is2\Computer_Icon.png
D:\Documents\Obrázky\is2\Key-icon.png D:\Documents\Obrázky\is2\Key-icon.png
D:\Documents\Obrázky\is2\Key-icon.png
Signature
D:\Documents\Obrázky\is2\Phone-icon.png D:\Documents\Obrázky\is2\Computer_Icon.png
D:\Documents\Obrázky\is2\Key-icon.png D:\Documents\Obrázky\is2\Key-icon.png
D:\Documents\Obrázky\is2\Key-icon.png
Signature
Signature
D:\Documents\Obrázky\is2\Phone-icon.png D:\Documents\Obrázky\is2\Key-icon.png
Signature
Multiple signatures
Threshold
Signature (MPC)
A hand holding a pen Description automatically generated with medium confidence
D:\Documents\Obrázky\is2\User-Group-icon.png
Signature
Analogically for decryption (single person decrypts, multiple people, k-of-n)
Shamir TSS
Share 3
Share 2
Share 1

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
How to “split” key for threshold cryptography?
•(Shamir threshold secret sharing)
•
•Multiple separate signatures (same algorithm)
•
•Cryptographic “garden” (multiple keys, different keys)
•
•n-of-n MPC signature (multiple keys, all must contribute)
–k-of-n MPC threshold signature (multiple keys, k must contribute)
30
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
D:\Documents\Obrázky\is2\Key-icon.png D:\Documents\Obrázky\is2\Key-icon.png
D:\Documents\Obrázky\is2\Key-icon.png D:\Documents\Obrázky\is2\Key-icon.png
Signature
ECC
PQC
Signature
RSA
RSA
31

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
•
32
D:\Documents\Obrázky\is2\Phone-icon.png D:\Documents\Obrázky\is2\Computer_Icon.png
D:\Documents\Obrázky\is2\Key-icon.png D:\Documents\Obrázky\is2\Key-icon.png
D:\Documents\Obrázky\is2\Key-icon.png
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 / k-of-n)
–Number of communication rounds
–Computation complexity
–Security assumptions…
[USEMAP]
D:\Documents\Obrázky\is2\Phone-icon.png D:\Documents\Obrázky\is2\Computer_Icon.png
D:\Documents\Obrázky\is2\Key-icon.png D:\Documents\Obrázky\is2\Key-icon.png
D:\Documents\Obrázky\is2\Key-icon.png

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
PRACTICAL EXAMPLES OF MPC
•
34
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
D:\Documents\Obrazky\is2\Home-Server-icon.png
6k RSA Signature
D:\Documents\Obrázky\is2\Phone-icon.png
Sign 3k RSA
Sign 3k RSA
35

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
36
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 two MPC 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
37
PV204 | Secure Multiparty Computation
https://arxiv.org/pdf/1810.04660.pdf

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
D:\Documents\Obrázky\is2\Plain-Blue-icon.png
Cryptography as a Service (CaaS)
D:\Documents\Obrázky\is2\Computer_Icon.png D:\Documents\Obrázky\is2\Key-icon.png
D:\Documents\Obrázky\is2\Plain-Blue-icon.png
WS API: JSON
D:\Documents\Obrázky\is2\Plain-Blue-icon.png D:\Documents\Obrázky\is2\Computer_Icon.png
D:\Documents\Obrázky\is2\Computer_Icon.png D:\Documents\Obrázky\is2\Computer_Icon.png
D:\Documents\Obrázky\is2\Computer_Icon.png D:\Documents\Obrázky\is2\Computer_Icon.png
D:\Documents\Obrázky\is2\Computer_Icon.png
Hardware Security
Module (HSM)
PV204 | Secure Multiparty Computation
38
•CaaS creates single point of failure (SPoF)
–More risk to server
•Typically solved by HSM
•HSM becomes SPoF!
•
•

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
•
39
PV204 | Secure Multiparty Computation
https://crocs.fi.muni.cz/papers/space2015
D:\Documents\Develop\SmartHSM\doc\INitial_grid_cards_800px.jpg
First prototype:
12+2 configuration
C:\Picts\Cambridge2015\Hardware\IMG_1960_s.jpg
1U prototype:
43+2 configuration
Dedicated board:
110+10 cards configuration
Performance:
~600 RSA-1024 signs/sec
~1200 HMAC/sec
CryptoHive

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
8300-ACOS2-8K
Problem: buggy or subverted chip
40
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
D:\Documents\Obrázky\is2\Phone-icon.png D:\Documents\Obrázky\is2\Computer_Icon.png

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
41

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
How to run MPC on JavaCards
•MPC applets: https://github.com/OpenCryptoProject/Myst, https://github.com/crocs-muni/JCFROST
•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
•
42
PV204 | Secure Multiparty Computation
Shape Description automatically generated
https://github.com/OpenCryptoProject/JCMathLib

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
43

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Graphical user interface, text, application, email Description automatically generated
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 Computation
44

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Diagram Description automatically generated
45
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
USE-CASE SCENARIOS
•
46
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
High-level usage scenarios
1.Digital signature
2.User authentication
3.Data decryption
4.Key / randomness generation
47
PV204 | Secure Multiparty Computation

Díky zpětně kompatibilnímu MPC lze zvýšit bezpečnost i tam, kde to teď není možné bez přechodu na
nový systém (více podepisujících, lepší kontrola autentizace, lepší kontrola přístupu k datům)

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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)
48
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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)
•
49
PV204 | Secure Multiparty Computation
A picture containing text, sign Description automatically generated

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
50
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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)
•
51
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Threshold crypto protocols – tradeoffs and limitations
•Security vs. usability
•More difficult to finalize signature (more parties, communication)
•More complex software (bugs more likely)
•Number of rounds, interaction
•Amount of data exchanged
•Active research field => possibility for new attacks against whole schemes
•
52
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Backward compatibility
•Existing systems already use some crypto algorithm (RSA, ECDSA…)
–Difficult to switch all information systems to new algorithm
•Threshold algorithm is backward compatible, if verification is unchanged
–Only signer needs to update its software (to create threshold MPC signature)
–Verification software stay unchanged
–Allows for gradual opt-in (improve signing security of people who upgrade)
–(similarly for decryption – if encryption is unchanged)
•Backward-compatible signatures exists for commonly used algorithms
–RSA, ECDSA, EdDSA, Schnorr…
53
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
54
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
•
55
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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)
•
56
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
•
•
•
57
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
HOW TO PROTECT
•Protections Against Reverse Engineering
PV204 | Secure Multiparty Computation
58

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Standard vs. whitebox attacker model
(symmetric crypto example)
PV204 | Secure Multiparty Computation
59

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
60

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
61

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
CEF&CED
•Computation with Encrypted Data and Encrypted Function
PV204 | Secure Multiparty Computation
62

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
63

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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)
•
•
•
•
64
PV204 | Secure Multiparty Computation
A
B

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
65
PV204 | Secure Multiparty Computation
A
B

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
66

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
67

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Partial homomorphic schemes
•Example with RSA (multiplication)
–E(d1).E(d2) = d1e . d2e mod m = (d1d2)e mod m = E(d1d2)
•Example Goldwasser-Micali (addition)
–E(d1).E(d2) = xd1r12 . Xd2r22 = 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 Computation
68

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
69
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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)
–
70
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
71

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
Fully homomorphic scheme - practicality
•Not very practical (yet J) (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 Computation
72

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
–
–
•
73
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
WHITEBOX CRYPTOGRAPHY
•
74
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
75

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
PV204 | Secure Multiparty Computation
Whitebox transform
76

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
2128
77

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
78

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
79

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
PV204 | Secure Multiparty Computation
80

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
81

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
•
PV204 | Secure Multiparty Computation
makeTable()
precompTable
data
encrypted data
encrypt(data)
AES
key
Environment under control
of an attacker
Environment outside control
of an attacker
82

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
83

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
84

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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/
85

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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
86
PV204 | Secure Multiparty Computation

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 L
–several former schemes broken
–new techniques being proposed
PV204 | Secure Multiparty Computation
87

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
88

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
89

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
90

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          https://crocs.fi.muni.cz @CRoCS_MUNI
BGE attack in progress
PV204 | Secure Multiparty Computation
91

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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:mobilecrypto
•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 Computation
92

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
          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 Computation
93