UUID는 얼마나 독특합니까?
https://stackoverflow.com/questions/1155008
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
UUID를 사용하여 무언가를 고유하게 식별하는 것이 얼마나 안전합니까(저는 서버에 업로드된 파일에 사용하고 있습니다)?내가 이해하는 바에 따르면 이는 난수를 기반으로 합니다.그러나 충분한 시간이 주어지면 순전히 우연에 따라 결국 스스로 반복하게 될 것 같습니다.이 문제를 완화할 수 있는 더 나은 시스템이나 특정 유형의 패턴이 있습니까?
해결책
매우 안전:
주어진 사람이 운석에 부딪히는 연간 위험은 170 억의 기회로 추정됩니다. 이는 확률이 약 0.00000000006 (6 × 10입니다.−11), 1 년 안에 수십 억 개의 UUID를 생성 할 확률과 동일합니다.다시 말해, 향후 100 년 동안 매 초마다 10 억 개의 UUID를 생성 한 후에 만 하나의 복제본 만 생성 할 확률은 약 50%입니다.
경고:
그러나 이러한 확률은 충분한 엔트로피를 사용하여 UUID가 생성 될 때만 유지됩니다.그렇지 않으면, 통계적 분산이 더 낮을 수 있기 때문에, 복제 가능성은 상당히 높을 수있다.분산 응용 프로그램에 고유 식별자가 필요한 경우, 많은 장치의 데이터가 병합 될 때에도 UUID가 충돌하지 않도록 모든 장치에서 사용되는 종자 및 발전기의 무작위성은 애플리케이션 수명에 신뢰할 수 있어야합니다.이것이 가능하지 않은 경우, RFC4122는 대신 네임 스페이스 변형을 사용하는 것이 좋습니다.
원천:그만큼 무작위 UUID 중복 확률 부분 Universally Unique Identifiers에 대한 Wikipedia 기사(링크는 해당 섹션을 편집하기 전인 2016년 12월의 개정판으로 연결됨).
또한 동일한 범용 고유 식별자 기사에서 동일한 주제에 대한 현재 섹션을 참조하세요. 충돌.
다른 팁
"충분한 시간을 주어 주면"당신이 100 년을 의미하고 초 10 억의 속도로 그들을 만들고 있다면, 100 년 후에 충돌을 일으킬 확률이 50%입니다.
UUID의 유형이 두 개 이상 있으므로 "안전"은 사용중인 유형 (UUID 사양이 "버전")에 따라 다릅니다.
버전 1은 시간 기반 Plus Mac 주소 UUID입니다. 128 비트에는 네트워크 카드의 MAC 주소 (제조업체가 고유하게 할당)에 48 비트와 100 나노 초의 해상도가있는 60 비트 시계가 포함되어 있습니다. 그 시계 3603 년에 랩 따라서이 UUID는 적어도 그때까지 안전합니다 (초당 1 천만 개 이상의 새로운 UUID가 필요하지 않거나 누군가가 네트워크 카드를 복제하지 않는 한). 나는 1582 년 10 월 15 일에 시계가 시작되기 때문에 "적어도"라고 말하기 때문에, 중복의 가능성이 적기 전에 시계가 랩 된 후 약 400 년이 걸렸다.
버전 4는 랜덤 번호 UUID입니다. 6 개의 고정 비트가 있으며 나머지 UUID는 122 비트의 임의성입니다. 보다 위키 백과 또는 복제본이 얼마나 가능성이 낮은 지 설명하는 다른 분석.
버전 3은 MD5를 사용하고 버전 5는 SHA-1을 사용하여 무작위 또는 의사 랜덤 번호 생성기 대신 122 비트를 만듭니다. 따라서 안전 측면에서 그것은 버전 4가 통계적 문제인 것과 같습니다 (Digest 알고리즘이 처리하는 것이 항상 고유한지 확인하는 한).
버전 2는 버전 1과 비슷하지만 시계가 작은 경우 훨씬 더 빨리 감싸게됩니다. 그러나 버전 2 UUID는 DCE를위한 것이므로 사용해서는 안됩니다.
따라서 모든 실제 문제에 대해 안전합니다. 당신이 그것을 확률로 맡기는 것이 불편하다면 (예 : 평생 동안 큰 소행성에 의해 지구가 파괴되는 것에 대해 걱정하는 사람의 유형), 버전 1 UUID를 사용하고 독특한 것으로 보장하십시오 (독특한 것으로 보장하십시오). 일생 동안, 당신이 3603 년을 지나서 살 계획이 아니라면)).
그렇다면 왜 모든 사람이 단순히 버전 1 UUID를 사용하지 않습니까? 이는 버전 1 UUID가 생성 된 컴퓨터의 MAC 주소를 드러내고 예측할 수 있기 때문에 UUID를 사용하여 응용 프로그램에 보안에 영향을 줄 수있는 두 가지를 예측할 수 있기 때문입니다.
이에 대한 답은 대부분 UUID 버전에 달려있을 수 있습니다.
많은 UUID 생성기는 버전 4 랜덤 번호를 사용합니다. 그러나, 이들 중 다수는 Pseudo를 무작위 숫자 생성기를 사용하여이를 생성합니다.
적은시기가있는 씨앗이 제대로 뿌려진 PRNG가 UUID를 생성하는 데 사용된다면 전혀 안전하지 않다고 말할 것입니다.
따라서 알고리즘을 생성하는 데 사용되는 알고리즘만큼 안전합니다.
반대로,이 질문에 대한 답을 알고 있다면 버전 4 UUID는 사용하기에 매우 안전해야한다고 생각합니다. 실제로 네트워크 블록 파일 시스템에서 블록을 식별하는 데 사용하고 지금까지 충돌이 없었습니다.
제 경우에는 내가 사용하고있는 PRNG는 Mersenne Twister이며 /dev /urandom을 포함한 여러 출처에서 나오는 시드 방식에주의를 기울이고 있습니다. Mersenne Twister의 기간은 2^19937-1입니다.
인용 위키 백과:
따라서 누구나 UUID를 만들어 사용하여 식별자가 다른 사람이 의도하지 않은 사람이 결코 사용하지 않을 것이라는 합리적인 확신을 가지고 무언가를 식별 할 수 있습니다.
실제로 얼마나 안전한 지에 대해 자세히 설명하는 것이 계속됩니다. 따라서 귀하의 질문에 답하기 위해 : 예, 충분히 안전합니다.
UUID 체계는 일반적으로 의사 랜덤 요소뿐만 아니라 현재 시스템 시간과 네트워크 MAC 주소와 같은 경우에도 종종 단단한 하드웨어 ID를 사용합니다.
UUID를 사용하는 요점은 자신이 할 수있는 것보다 고유 한 ID를 제공하는 더 나은 일을한다고 믿는다는 것입니다. 이것은 자신의 출시 대신 제 3 자 암호화 라이브러리를 사용하는 것과 동일한 근거입니다. 스스로하는 것이 더 재미있을 수 있지만 일반적으로 그렇게하는 것은 덜 책임이 있습니다.
몇 년 동안하고 있습니다. 문제를 해결하지 마십시오.
나는 보통 모든 키와 수정 날짜 등이 포함 된 테이블 하나를 갖도록 DB를 설정했습니다. 중복 키의 문제를 해결하지 못했습니다.
유일한 단점은 키를 빨리 찾기 위해 몇 가지 정보를 찾기 위해 몇 가지 쿼리를 작성하는 것입니다. 키의 많은 복사 및 붙여 넣기를 수행하는 것입니다. 더 이상 기억하기 쉬운 짧은 ID가 없습니다.
다음은 독창적 인 테스트 스 니펫입니다. @scalabl3의 의견에서 영감을 얻었습니다
재미있는 것은, 당신은 물론, 우연의 일치, 행운 및 신성한 개입의 마음을 사로 잡는 수준에서 동일한 연속으로 2를 생성 할 수 있다는 것입니다. 그러나 헤아릴 수없는 확률에도 불구하고 여전히 가능합니다! : D 예, 일어나지 않을 것입니다. 중복을 만들었을 때 그 순간에 대한 생각의 즐거움을 위해 말하는 것입니다! 스크린 샷 비디오! - SCALABL33 10 월 20 '15 at 19:11
운이 좋다고 생각되면 확인란을 확인하면 현재 생성 된 ID 만 확인합니다. 역사 확인을 원한다면 확인하지 않으십시오. 확인하지 않으면 어느 시점에서 RAM이 부족할 수 있습니다. CPU 친화적으로 만들려고 노력 했으므로 필요할 때 빨리 중단하거나 실행 스 니펫 버튼을 다시 누르거나 페이지를 남겨 둡니다.
Math.log2 = Math.log2 || function(n){ return Math.log(n) / Math.log(2); }
Math.trueRandom = (function() {
var crypt = window.crypto || window.msCrypto;
if (crypt && crypt.getRandomValues) {
// if we have a crypto library, use it
var random = function(min, max) {
var rval = 0;
var range = max - min;
if (range < 2) {
return min;
}
var bits_needed = Math.ceil(Math.log2(range));
if (bits_needed > 53) {
throw new Exception("We cannot generate numbers larger than 53 bits.");
}
var bytes_needed = Math.ceil(bits_needed / 8);
var mask = Math.pow(2, bits_needed) - 1;
// 7776 -> (2^13 = 8192) -1 == 8191 or 0x00001111 11111111
// Create byte array and fill with N random numbers
var byteArray = new Uint8Array(bytes_needed);
crypt.getRandomValues(byteArray);
var p = (bytes_needed - 1) * 8;
for(var i = 0; i < bytes_needed; i++ ) {
rval += byteArray[i] * Math.pow(2, p);
p -= 8;
}
// Use & to apply the mask and reduce the number of recursive lookups
rval = rval & mask;
if (rval >= range) {
// Integer out of acceptable range
return random(min, max);
}
// Return an integer that falls within the range
return min + rval;
}
return function() {
var r = random(0, 1000000000) / 1000000000;
return r;
};
} else {
// From http://baagoe.com/en/RandomMusings/javascript/
// Johannes Baagøe <baagoe@baagoe.com>, 2010
function Mash() {
var n = 0xefc8249d;
var mash = function(data) {
data = data.toString();
for (var i = 0; i < data.length; i++) {
n += data.charCodeAt(i);
var h = 0.02519603282416938 * n;
n = h >>> 0;
h -= n;
h *= n;
n = h >>> 0;
h -= n;
n += h * 0x100000000; // 2^32
}
return (n >>> 0) * 2.3283064365386963e-10; // 2^-32
};
mash.version = 'Mash 0.9';
return mash;
}
// From http://baagoe.com/en/RandomMusings/javascript/
function Alea() {
return (function(args) {
// Johannes Baagøe <baagoe@baagoe.com>, 2010
var s0 = 0;
var s1 = 0;
var s2 = 0;
var c = 1;
if (args.length == 0) {
args = [+new Date()];
}
var mash = Mash();
s0 = mash(' ');
s1 = mash(' ');
s2 = mash(' ');
for (var i = 0; i < args.length; i++) {
s0 -= mash(args[i]);
if (s0 < 0) {
s0 += 1;
}
s1 -= mash(args[i]);
if (s1 < 0) {
s1 += 1;
}
s2 -= mash(args[i]);
if (s2 < 0) {
s2 += 1;
}
}
mash = null;
var random = function() {
var t = 2091639 * s0 + c * 2.3283064365386963e-10; // 2^-32
s0 = s1;
s1 = s2;
return s2 = t - (c = t | 0);
};
random.uint32 = function() {
return random() * 0x100000000; // 2^32
};
random.fract53 = function() {
return random() +
(random() * 0x200000 | 0) * 1.1102230246251565e-16; // 2^-53
};
random.version = 'Alea 0.9';
random.args = args;
return random;
}(Array.prototype.slice.call(arguments)));
};
return Alea();
}
}());
Math.guid = function() {
return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function(c) {
var r = Math.trueRandom() * 16 | 0,
v = c == 'x' ? r : (r & 0x3 | 0x8);
return v.toString(16);
});
};
function logit(item1, item2) {
console.log("Do "+item1+" and "+item2+" equal? "+(item1 == item2 ? "OMG! take a screenshot and you'll be epic on the world of cryptography, buy a lottery ticket now!":"No they do not. shame. no fame")+ ", runs: "+window.numberofRuns);
}
numberofRuns = 0;
function test() {
window.numberofRuns++;
var x = Math.guid();
var y = Math.guid();
var test = x == y || historyTest(x,y);
logit(x,y);
return test;
}
historyArr = [];
historyCount = 0;
function historyTest(item1, item2) {
if(window.luckyDog) {
return false;
}
for(var i = historyCount; i > -1; i--) {
logit(item1,window.historyArr[i]);
if(item1 == history[i]) {
return true;
}
logit(item2,window.historyArr[i]);
if(item2 == history[i]) {
return true;
}
}
window.historyArr.push(item1);
window.historyArr.push(item2);
window.historyCount+=2;
return false;
}
luckyDog = false;
document.body.onload = function() {
document.getElementById('runit').onclick = function() {
window.luckyDog = document.getElementById('lucky').checked;
var val = document.getElementById('input').value
if(val.trim() == '0') {
var intervaltimer = window.setInterval(function() {
var test = window.test();
if(test) {
window.clearInterval(intervaltimer);
}
},0);
}
else {
var num = parseInt(val);
if(num > 0) {
var intervaltimer = window.setInterval(function() {
var test = window.test();
num--;
if(num < 0 || test) {
window.clearInterval(intervaltimer);
}
},0);
}
}
};
};Please input how often the calulation should run. set to 0 for forever. Check the checkbox if you feel lucky.<BR/>
<input type="text" value="0" id="input"><input type="checkbox" id="lucky"><button id="runit">Run</button><BR/>나는 다른 대답에 동의합니다. UUID는 거의 모든 실제 목적으로 충분히 안전합니다1, 그리고 확실히 당신을 위해.
그러나 (가설 적으로) 그들이 그렇지 않다고 가정하십시오.
이 문제를 완화하기 위해 더 나은 시스템이나 어떤 유형의 패턴이 있습니까?
다음은 몇 가지 접근 방식입니다.
더 큰 uuid를 사용하십시오. 예를 들어, 128 임의 비트 대신 256 또는 512 또는 ... Type-4 스타일에 추가하는 각 비트를 사용하여 충돌 확률을 절반으로 줄입니다.2.
UUID를 생성하고 발행 한 모든 것을 기록하는 중앙 집중식 또는 분산 서비스를 구축하십시오. 새로운 것을 생성 할 때마다 UUID가 이전에 발행 된 적이 없는지 확인합니다. 우리가 서비스를 운영하는 사람들이 절대적으로 신뢰할 수 있고 부패 할 수 없다고 가정하면 이러한 서비스는 기술적으로 구현하기가 직선적입니다 (제 생각에는 생각합니다). 불행히도, 그들은 특히 정부가 방해 할 가능성이있을 때 특히 그렇지 않습니다. 따라서이 접근법은 아마도 비현실적 일 수 있으며3 현실 세계에서는 불가능합니다.
1- UUID의 독창성이 귀하의 국가 수도에서 핵 미사일이 발사되었는지 여부를 결정하면 많은 동료 시민들이 "확률이 매우 낮습니다"에 의해 확신되지 않을 것입니다. 따라서 나의 "거의 모든"자격.
2- 그리고 여기 당신에게 철학적 질문이 있습니다. 진정으로 무작위가 있습니까? 그렇지 않은지 어떻게 알 수 있습니까? 우리가 알고있는 우주는 시뮬레이션입니까? 결과를 바꾸기 위해 물리 법칙을 "조정"할 수있는 신이 있습니까?
3-이 문제에 대한 연구 논문을 알고 있다면 의견을 제시하십시오.
이것이 당신에게 중요한지 모르겠지만 안내는 전 세계적으로 독특하지만 Guid의 하위 문자열은 아닙니다..
