LeakLWE2/Sec6_applications/exploiting_SCA_attack.sage

#!/usr/bin/sage -python
# -*- coding: latin-1 -*-

load("../framework/instance_gen.sage")

for params in ['CCS1']:
    logging("Set of parameters: " + params)

    if params == 'challenge':
        n = 296
        m = n + 4
        q = 2**12
        frodo_distribution = []
        D_s = {-1: RR(1 / 3), 0: RR(1 / 3), 1: RR(1 / 3)}

    elif params == 'NIST1':
        # NIST1 FRODOKEM-640
        n = 640
        m = 640
        q = 2**15
        frodo_distribution = [9288, 8720, 7216, 5264, 3384,
                                1918, 958, 422, 164, 56, 17, 4, 1]
        D_s = get_distribution_from_table(frodo_distribution, 2 ** 16)
        load("Frodo_Single_data/simulation_distribution_NIST1.sage")
        load("Frodo_Single_data/aposteriori_distribution_NIST1.sage")

    elif params == 'NIST2':
        # NIST2 FRODOKEM-976
        n = 976
        m = 976
        q = 65536
        frodo_distribution = [11278, 10277, 7774, 4882, 2545, 1101,
                                 396, 118, 29, 6, 1]
        D_s = get_distribution_from_table(frodo_distribution, 2 ** 16) 
        load("Frodo_Single_data/simulation_distribution_NIST2.sage")
        load("Frodo_Single_data/aposteriori_distribution_NIST2.sage")

    elif params == 'CCS1':
        n = 352
        m = 352
        q = 2 ** 11
        frodo_distribution = [22528, 15616, 5120, 768]
        D_s = get_distribution_from_table(frodo_distribution, 2 ** 16)
        load("Frodo_Single_data/simulation_distribution_CCS1.sage")
        load("Frodo_Single_data/aposteriori_distribution_CCS1.sage")

    elif params == 'CCS2':
        n = 592
        m = 592
        q = 2 ** 12
        frodo_distribution = [25120, 15840, 3968, 384, 16]
        D_s = get_distribution_from_table(frodo_distribution, 2 ** 16) 
        load("Frodo_Single_data/simulation_distribution_CCS2.sage")
        load("Frodo_Single_data/aposteriori_distribution_CCS2.sage")

    elif params == 'CCS3':
        n = 752
        m = 752
        q = 2 ** 15
        frodo_distribution = [19296, 14704, 6496, 1664, 240, 16]
        D_s = get_distribution_from_table(frodo_distribution, 2 ** 16) 
        load("Frodo_Single_data/simulation_distribution_CCS3.sage")
        load("Frodo_Single_data/aposteriori_distribution_CCS3.sage")

    elif params == 'CCS4':
        n = 864
        m = 864
        q = 2 ** 15
        frodo_distribution = [19304, 14700, 6490, 1659, 245, 21, 1]
        D_s = get_distribution_from_table(frodo_distribution, 2 ** 16) 
        load("Frodo_Single_data/simulation_distribution_CCS4.sage")
        load("Frodo_Single_data/aposteriori_distribution_CCS4.sage")


    """  Original Security   """

    A, b, dbdd = initialize_from_LWE_instance(DBDD_predict_diag,
                                               n,
                                               q, m, D_s, D_s, verbosity=0)
    dbdd.integrate_q_vectors(q, indices=range(n, n + m))
    (beta, _) = dbdd.estimate_attack()
    logging("Attack without hints:  %3.2f bikz" % beta, style="HEADER")

    """  Refined Side channel attack  """

    def simu_measured(secret):
        """ 
        This fonction simulates the information gained by
        Bos et al attack. The simulation is based on a
        distribution obtained with a large amount of data
        for Bos et al suite (in Matlab).
        :secret: an integer being the secret value
        :measurement: an integer that represents the output
        of Bos et al attack.
        """
        secret = recenter(secret)
        distrib_of_guesses = renormalize_dist(Dguess[secret])
        measurement = draw_from_distribution(distrib_of_guesses)
        return measurement


    def ordered_indices(sorted_guesses, measured):
            """
            Necessary for the bruteforce attack, this function
            sorts the indices of the coefficients
            of the secret with decreasing likelihood.
            :sorted_guess: the best guesses in order of likelihood
            :measured: the measurement for each coefficient
            :orderered_coefficients: the indices of the coefficients
            ordered according to Probability[secret[i] = measured[i]]
            """
            orderered_coefficients = []
            for x in sorted_guesses:
                for i in range(len(measured)):
                    meas = measured[i]
                    if meas == x:
                        orderered_coefficients += [i]
            return orderered_coefficients


    def estimate_SCA(report_every, dbdd, measured, max_guesses):
        """ 
        This function evaluates the security loss after Bos et al attack
        :report_every: an integer that give the frequency of
        logging (None for no logging)
        :dbdd: instance of the class DBDD
        :measured: table representing the (simulated) information
        given by Bos et al attack
        :max_guesses: integer for upperbounding the number of guesses
        """

        Id = identity_matrix(n + m)
        for i in range(n):
            v = vec(Id[i])
            if report_every is not None and ((i % report_every == 0) or (i == n - 1)) :
                verbose = 2 
            else:
                verbose = 0
            dbdd.verbosity = verbose
            if verbose == 2:
                logging("[...%d]" % report_every, newline=False)
            if variance_aposteriori[measured[i]] is not None and variance_aposteriori[measured[i]] != 0:
                dbdd.integrate_approx_hint(v,
                                           center_aposteriori[measured[i]],
                                           variance_aposteriori[measured[i]],
                                           aposteriori=True, estimate=verbose)
            elif variance_aposteriori[measured[i]] is not None and variance_aposteriori[measured[i]] == 0 :
                dbdd.integrate_perfect_hint(v, center_aposteriori[measured[i]],
                                            estimate=verbose)
        if report_every is not None:
            dbdd.integrate_q_vectors(q, indices=range(n, n + m), report_every=report_every)
        else:
            dbdd.integrate_q_vectors(q, indices=range(n, n + m))
        (beta, _) = dbdd.estimate_attack()

        if report_every is not None:
            logging("     Hybrid attack estimation     ", style="HEADER")

        sorted_guesses = sorted(proba_best_guess_correct.items(),
                                key=lambda kv: - kv[1])
        sorted_guesses = [sorted_guesses[i][0] for i in range(len(sorted_guesses))
                          if sorted_guesses[i][1] != 1.]
        proba_success = 1.
        dbdd.verbosity = 0
        guesses = 0
        j = 0
        for i in ordered_indices(sorted_guesses, measured):
            j += 1
            if (guesses <= max_guesses):
                v = vec(Id[i])
                if dbdd.integrate_perfect_hint(v, _):
                    guesses += 1
                    proba_success *= proba_best_guess_correct[measured[i]]
                if report_every is not None and (j % report_every == 0):
                    logging("[...%d]" % report_every, newline=False)
                    dbdd.integrate_q_vectors(q, indices=range(n, n + m))
                    logging("dim=%3d \t delta=%.6f \t beta=%3.2f \t guesses=%4d" %
                            (dbdd.dim(), dbdd.delta, dbdd.beta, guesses),
                            style="VALUE", newline=False)
                    logging("Proba success = %s" % proba_success, style="VALUE",
                            newline=True)
        dbdd.attack()
        return beta, dbdd.beta, proba_success



    """  Example
    Uncomment the following to get the detailed computation
    """

    A, b, dbdd = initialize_from_LWE_instance(DBDD,
                                                  n,
                                                  q, m, D_s, D_s, verbosity=2)
    measured = [simu_measured(dbdd.u[0, i]) for i in range(n)]
    estimate_SCA(50, dbdd, measured, 200)