wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Security by obscurity in 100 bits
        
(Message started by: ephyzy on Jun 13^th, 2016, 4:31am)

Title: Security by obscurity in 100 bits
Post by ephyzy on Jun 13^th, 2016, 4:31am

A "security by obscurity" system uses a 100 bits access code, with only 12 bits set. On the first day, it had a random access code of 100 bits. Then at the end of the day, it collects all the N intrusion attempts for the day (each one is 100 bits, with only 6 set bits) and updates its access code for the next day.
This update is done in such a way that:
- a% is correct on any 6 set bits,
- b% is correct on any 5 set bits,
- c% is correct on any 4 set bits,
- d% is correct on any 3 set bits,
- e% is correct on any 2 set bits
- f% is correct on any 1 set bit
- g% is correct on no set bits
- If all the bits set by the above 7 rules are less than 12, the system sets some random bits to make up the 12.

Q1: How must the new access code be generated at the end of the day, in terms of N intrusion attempts and the positive real numbers a, b, c, d, e, f, g (generated by the system such that the sum of these 7 is exactly 100)?

Q2: Question 1, but for fixed values of a,b,c,d,e,f and g on every day.

P.S. The system only provides direct access to set 6 bits. An intruder does not know that it is 12 bits that will need to be set, as the other 6 bits are hidden.

Title: Re: Security by obscurity in 100 bits
Post by ephyzy on Jun 14^th, 2016, 4:01am

Alternative problem statement:

Each of matrices P, Q, R is a column matrix with 100 bit binary numbers.

Given a matrix P, where each entry has exactly 6 set bits but the rows are not necessarily identical. What strategies / procedures can be used to generate a matrix Q with identical rows (some binary number with any 12 bits set) such that upon taking a bitwise AND of P and Q (i.e. P & Q) we may obtain any matrix R whose entries have set bits that have a known statistical distribution between 0 and 6?

Title: Re: Security by obscurity in 100 bits
Post by towr on Jun 18^th, 2016, 1:14pm

I don't really fancy my chances that it's even possible to get close to a given statistical distribution.
If it is, brute force seems almost doable, 100!/(88! * 12!) is only in the order of 10^15.
How large is N?

Title: Re: Security by obscurity in 100 bits
Post by ephyzy on Jun 18^th, 2016, 2:06pm

@towr:
Thanks! N can be as large as possible, and that's why I am wondering if there is a more efficient way to solve the problem that will scale well even for large N.

I eventually solved this in a way that involves minimal randomization (successively choosing 2 or 3 random integers), and also involves some bitwise OR and AND operations, but I feel sure there is probably a better way to do it.

Title: Re: Security by obscurity in 100 bits
Post by ephyzy on Nov 19^th, 2024, 2:47am

Any ideas or takers for the alternative problem statement? My Python code in 2016 was actually wrong, as I found out about a month later. Seeking a non-brute force method if possible. The upper limit of N is 10^9.