Closer to Code

MySQLowy autoincrement jest bez wątpienia potężnym i wygodnym mechanizmem. Jest też bardzo popularny. I trudno się dziwić ;) ustaw - zapomnij. Wygodne prawda? Jednak takie podejście niesie za sobą pewne nieciekawe konsekwencje.

Korzystając z interfejsu RESTowego jesteśmy zmuszeni (aczkolwiek raczej nikomu to nie przeszkadza ;) ) do używania identyfikatorów na zasadzie: artykuly/1234/komentarze/2156 gdzie mamy id artykułu i id komentarza.

Ale co w tym złego?

Niby nic - liczby jak każde inne. Jednak tutaj zaczyna się problem, ponieważ liczby te po pierwsze mogą nam powiedzieć dość dużo same z siebie - kiedy ustawione są na autoincrement numerowane są w kolejności powstania. Dzięki temu ktoś uważny jest w stanie ocenić jak dużo mamy komentarzy/logów/wpisów/zdjęć w systemie, nawet jeśli część nie jest dla niego dostępna.

Ciekawostka: Takiej metody użyli alianci żeby ocenić poziom produkcji czołgów niemieckich. Numery seryjne czołgów były właśnie inkrementowane.

Kolejną rzeczą jest bezpieczeństwo. Oczywiście stosujemy white listy i inne metody weryfikacji uprawnień użytkowników. Stosujemy też testy żeby sprawdzić czy wszystko jest należycie zabezpieczone. Niemniej jednak nie sposób uchronić się od wszystkich błędów.

Sprytny użytkownik

Załóżmy że mamy logi systemowe - część logów może przeglądać każdy użytkownik (te które dotyczą właśnie jego) a część tylko admin. No i implementujemy sobie podgląd danego logu w akcji show, gdzie w URLu podajemy ID.

Oczywistym rozwiązaniem byłoby zastosowanie filtra, który sprawdzałby uprawnienia i ew. odnotował że ten i ten user stara się uzyskać dostęp do zasobów chronionych. Jednak przez nieuwagę zapomnieliśmy to zrobić.

Co robi sprytny użytkownik?

Widząc że jego wpisy idą w miarę po kolei (np. 1, 5, 9,21, 23, ...) modyfikuje ręcznie URL i wchodzi na log o ID 2, 3, itd przeglądając rzeczy które teoretycznie powinny być dostępne tylko dla admina.

Inny sprytny pomysł

Dawno, dawno temu zamknięto serwis napisy.org i w polskim internecie zapanował strach wśród fanów anime że zamkną i świetny serwis animesub.info. Nie będę ukrywał że i ja się bałem ;) a że nie lubię siedzieć i czekać postanowiłem coś z tym zrobić. Za tamtych czasów serwis ten nie miał praktycznie żadnych zabezpieczeń, a pliki ściągać można było będąc niezalogowanym. Stosowano tam właśnie autoincrement dla plików. W bazie było ID pliku które jednocześnie było jego nazwą na dysku oraz był wpis w bazie do jakiego anime i odcinka jest ten plik.

Wystarczyło więc (wtedy jeszcze w delphi) napisać prosty program który będzie próbował pobrać wszystkie pliki od 0 do ostatniego (najnowszego). Metoda okazała się bardzo skuteczna. Aby nie wzbudzać podejrzeń pliki pobierane były z losowym delayem kilkusekundowym. Po dobie lokalna kopia ich bazy napisów była u mnie. Napisy usunąłem jak tylko potwierdzono że animesub zostaje :)

Na pocieszenie dodam że adminów animesub powiadomiłem i w miarę szybko zastosowali odpowiednie zabezpieczenia które skutecznie zabezpieczają obecnie ten system przed tego typu atakami.

Co zatem zrobić?

Osobiście znam dwa rozwiązania. Pierwszym z nich jest stosowanie GUIDów (Globally Unique Identifier) które wyglądają mniej więcej tak: 25892e17-80f6-415f-9c65-7395632f0223.

Jest to losowy ciąg cyfer oraz liter który generowany jest z jakiegoś skomplikowanego wzorca. W takim przypadku nie ma możliwości "jechania" po kolejnych wartościach bo jest ich po prostu za dużo.

Innym rozwiązaniem (które i ja stosuję troszkę częściej niż GUIDy) jest zrandomizowanie klucza głównego.

Implementacja tego rozwiązania jest bardzo prosta niezależnie od wybranego języka. Po prostu zamiast polegać na autoincremencie - losujemy ID z dużego zakresu (np. z miliona), sprawdzamy czy taki wpis już istnieje (na wszelki wypadek) i jeśli nie to dodajemy wpis. Jeśli tak to losujemy, sprawdzamy, dodajemy.

A jak to zrobić w Ruby on Rails?

A bardzo prosto. Pokusiłem się i napisałem nawet plugin który sam w sobie składa się z kilkunastu linijek, jednak według mnie jest bardzo wygodny. Nazwałem go acts_as_random co chyba oddaje w miarę sensownie jego funkcję.

Kod pluginu na licencji MIT (czyli rób z tym co chcesz ale jak coś nie będzie działać to też się nie czepiaj) dostępny do pobrania na końcu artykułu.

Jego użycie jest bardzo proste. Rozpakowujemy go do katalogu /vendor/plugins naszej aplikacji i od teraz możemy używać go w każdym modelu dziedziczącym po ActiveRecord.

Przykład:

class CoolClass < ActiveRecord::Base
    acts_as_random
end

Do naszego modelu dopisujemy tylko acts_as_random i już cała magia działa :) nic więcej nie trzeba robić a ID są generowane losowo, co można sprawdzić zapisując obiekt i wyświetlając jego id.

Oczywiście rozwiązanie moje nie jest wolne od wad. Przede wszystkim przy każdym zapisaniu obiektu następuje odpytanie czy obiekt o takim ID już nie istnieje (czyli +1 zapytanie do każdego save). Jeśli mamy system który generuje bardzo dużo danych warto pomyśleć nad GUIDami.

Kolejnym minusem jest to że jeśli będziemy mieli przykładowo 100 000 wpisów w danej tabeli a losujemy liczbę z przedziało 0..1 000 000 to mamy 10% szans że wylosujemy taką która już jest. Sprawia to że proces losowania musi być ponowiony i musi nastąpić kolejna weryfikacja ID (już +2 w tym wypadku do save'a).

W większości wypadków jednak losowanie z 1 000 000 w zupełności starcza a jeśli nie to zawsze można poprawić mój kod i zamiast z 1 000 000 losować z większego zakresu.

Rozwiązanie to jest wygodne (jedna linijka w modelu) i działa w większości przypadków - nie przeszkadzając przy tym w aplikacji (no chyba że ktoś korzysta z order by id).

Nie chroni ono w 100% jednak znacząco utrudnia życie potencjalnym "użyszkodnikom". Bo mając wpis o ID = 142145 następny może mieć wartość 235652, przez co szansa "trafienia" drastycznie spada w porównaniu z autoincrement.

Stosując to rozwiązanie oraz weryfikację uprawnień raczej nie powinno być problemów.

Jeśli więc tworzysz obiekty dużo rzadziej niż je wyświetlasz to to rozwiązanie jest dla Ciebie :)

Kod pluginu: acts_as_random

W związku z zajęciami z kryptografii, potrzebowałem mieć pod ręką trochę narzędzi umożliwiających obliczenie fi (funkcji Eulera), odwrotności modulo, rozkładu liczby na czynniki pierwsze, wyznaczanie odwrotności modulo macierzy 2x2 oraz mnożenie macierzy 2x2 razy 1x2 oraz obliczenia modulo z duuuuuużych liczb przedstawionych jako potęg. Dlatego też powstał kod działający na Androidzie. Jedyne wymaganie to Ruboto - do znalezienia na Markecie. Jest to JRuby dla Androida, umożliwiający odpalanie prostych skryptów na telefonie. Idealne kiedy trzeba napisać coś na szybko. Zaczniemy od potęgowania. Spróbuj dokonać takiego obliczenia modulo: 12345^12345 mod126 w kalkulatorze na Windows. Chyba się nie udało ;) A ten oto poniższy kod, świetnie sobie z tym radzi:

liczba = 12345
power = 12345
n = 126
#--------------------------------------
def mod(liczba, power, n)
  val = 1

  power.times do |i|
    val *= liczba
    val %= n
  end
  val
end

puts "#{liczba}^#{power}(mod#{n})= #{mod(liczba, power, n)}"

A wynikiem jest: 99 Następnie mamy funkcję Eulera (fi):

liczba = 30
#--------------------------------------
def phi(m)
  r = (2..m)
  primes = r.inject(r){|p, i| p.select{|n| n==i || n%i!=0}}
  primes.inject(m){|e, p| e%p==0 ? e/p*(p-1) : e}
end

puts "fi dla #{liczba} wynosi: #{phi(liczba)}"

Która też działa niczego sobie :) - oczywiście to obliczenie dla zbyt dużych liczb na telefonie komórkowym nie będzie przebiegać zbyt szybko, więc używajcie z rozwagą ;) Kolejnym kawałkiem kodu jest kod obliczający odwrotność zadanej liczby w sensie modulo:

liczba = 315
n = 676
#--------------------------------------

class Integer
  def to_ba(size=128)
    a=[]
    (size-1).downto(0) do |i|
      a<<< 2**index
  }

  val = 1
  powers.each { |pow|
    pow.times do |i|
      val *= liczba
      val %= n
    end
  }
  val
end

def check(liczba, odw, n)
  (liczba*odw)%n == 1
end

odw = odwrotnosc(liczba, n)

if odw == 0
  puts "Odwrotnosc nie istnieje NWD(#{liczba}, #{n}) != 1"
else

  if check(liczba, odw, n)
    puts "#{liczba}^-1 (mod#{n})= #{odw}"
  else
    puts "NWD(#{liczba}, #{n}) != 1"
  end
end

Rozkład liczby na czynniki pierwsze:

liczba = 2

# -----------------------------------------------------------------------------
def factorize(orig)
    factors = {}
    factors.default = 0
    n = orig
    i = 2
    sqi = 4
    while sqi <= n do
        while n.modulo(i) == 0 do
            n /= i
            factors[i] += 1
        end
        sqi += 2 * i + 1
        i += 1
    end

    if (n != 1) && (n != orig)
        factors[n] += 1
    end
    factors
end

def printfactorhash(orig, factorcount)
    print format("%-10d ", orig)
    if factorcount.length == 0
        print "Liczba pierwsza"
    else
        factorcount.sort.each { |factor,exponent|
            print factor
            if exponent > 1
                print "^", exponent
            end
            print " "
        }
    end
    puts
end

n = liczba.to_i
mfactors = factorize(n)
printfactorhash(n, mfactors)

Odwrotność macierzy (w sensie modulo):

MATRIX = [[0,11],
          [17,0]]

#[a, b]
#[c, d]

n = 29

#--------------------------------------

class Integer
  def to_ba(size=128)
    a=[]
    (size-1).downto(0) do |i|
      a<<self[i]
    end
    a
  end
end

def phi(m)
  r = (2..m)
  primes = r.inject(r){|p, i| p.select{|n| n==i || n%i!=0}}
  primes.inject(m){|e, p| e%p==0 ? e/p*(p-1) : e}
end

def odwrotnosc(liczba, n)
  fi = phi(n)

  powers = []
  (fi-1).to_ba.reverse.each_with_index { |b, index|
    next if b == 0
    powers << 2**index
  }

  val = 1
  powers.each { |pow|
    pow.times do |i|
      val *= liczba
      val %= n
    end
  }
  val
end

def nwd(a,b)
  if a > b then a -= b else b -= a end while a != b; return a
end

def det(m)
  m[0][0].to_i*m[1][1].to_i-m[0][1].to_i*m[1][0].to_i
end

def inverse(m, n)

  det = det(m)
  det = det%n

  if nwd(det, n) != 1
    puts "NWD(m, n) != 1"
    exit
  end

  puts "det= #{det}"
  odw_a = odwrotnosc(det, n)
  puts "det^-1mod(#{n})= #{odw_a}"

  w = []
  w << [odw_a*m[1][1]%n, -odw_a*m[0][1]%n ]
  w << [-odw_a*m[1][0]%n, odw_a*m[0][0]%n ]
  w
end

def print_res(w)
  puts "[#{w[0][0]}, #{w[0][1]}]"
  puts "[#{w[1][0]}, #{w[1][1]}]"
end

print_res(inverse(MATRIX, n))

Mnożenie macierzy 2x2 przez 1x2 (w sensie modulo n)

MATRIX1 = [
          [21,19],
          [22,18]]

MATRIX2 = [15, 24]

n = 29

def multiply(m1, m2, n)
  w = [(m1[0][0]*m2[0]+m1[0][1]*m2[1])%n, (m1[1][0]*m2[0]+m1[1][1]*m2[1])%n ]
end

def print_res(res)
  puts "[ #{res[0]}, #{res[1]}]"
end

print_res(multiply(MATRIX1, MATRIX2, n))

Podsumowując: powyżej zamieściłem kod który wykonuje następujące czynności:

Obliczanie modulo dużych liczb przedstawionych w postaci potęg
Funkcja Eulera - algorytm obliczenia wartości funkcji fi
Obliczanie odwrotności liczby w sensie modulo
Rozkład liczby na czynniki pierwsze

Mam nadzieję że się przyda :) A tutaj: źródełko

Page 161 of 171

Rails – losowe wartości klucza głównego – czyli dlaczego autoincrement to zło

Arytmetyka modulo + Ruboto + Ruby + Android