idnits 2.17.1 draft-thomson-geopriv-location-obscuring-03.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (June 27, 2011) is 4688 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: '-ve' is mentioned on line 1090, but not defined == Unused Reference: 'I-D.ietf-geopriv-arch' is defined on line 1252, but no explicit reference was found in the text == Outdated reference: A later version (-27) exists of draft-ietf-geopriv-policy-23 == Outdated reference: A later version (-08) exists of draft-thomson-geopriv-uncertainty-06 Summary: 0 errors (**), 0 flaws (~~), 5 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 GEOPRIV M. Thomson 3 Internet-Draft Andrew Corporation 4 Intended status: Informational June 27, 2011 5 Expires: December 29, 2011 7 Obscuring Location 8 draft-thomson-geopriv-location-obscuring-03.txt 10 Abstract 12 A method for obscuring location information is described. Both 13 static and changing location information can be obscured. A single 14 distance measure is input to the process; this parameter controls the 15 precision of location information that can be extracted by a 16 recipient. 18 Status of this Memo 20 This Internet-Draft is submitted in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on December 29, 2011. 35 Copyright Notice 37 Copyright (c) 2011 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 53 2. Method Characteristics and Applicability . . . . . . . . . . . 3 54 3. Obscuring Static Locations . . . . . . . . . . . . . . . . . . 4 55 3.1. Known Point Locations . . . . . . . . . . . . . . . . . . 5 56 3.2. Known Locations with Uncertainty . . . . . . . . . . . . . 5 57 3.3. Selecting a Offset Vector . . . . . . . . . . . . . . . . 6 58 3.3.1. Angle and Distance Method . . . . . . . . . . . . . . 6 59 3.3.2. Square Peg Method . . . . . . . . . . . . . . . . . . 7 60 3.3.3. Randomness Requirements . . . . . . . . . . . . . . . 8 61 3.4. Multiple Reported Locations . . . . . . . . . . . . . . . 8 62 4. Obscuring Changing Locations . . . . . . . . . . . . . . . . . 9 63 4.1. Update Conditions . . . . . . . . . . . . . . . . . . . . 9 64 4.1.1. Bad Triggers . . . . . . . . . . . . . . . . . . . . . 9 65 4.1.2. Hidden Trigger . . . . . . . . . . . . . . . . . . . . 10 66 4.2. Consecutive Reported Locations . . . . . . . . . . . . . . 11 67 4.2.1. Reducing Variation between Offset Vectors . . . . . . 12 68 4.2.2. Trade-off in Reducing Variation . . . . . . . . . . . 13 69 4.3. Returning to the Same Location . . . . . . . . . . . . . . 14 70 4.3.1. Positional Stability . . . . . . . . . . . . . . . . . 14 71 4.3.2. Triggering with Positional Stability . . . . . . . . . 15 72 4.3.3. Selecting a Grid . . . . . . . . . . . . . . . . . . . 15 73 4.3.4. Random Grid . . . . . . . . . . . . . . . . . . . . . 16 74 4.3.5. Linear Interpolation of Random Offsets . . . . . . . . 17 75 4.3.5.1. Uniformly Distributed Interpolation . . . . . . . 18 76 4.3.5.2. Applying Uniformly Distributed Interpolation . . . 20 77 4.3.5.3. Selecting an Appropriate Grid Size . . . . . . . . 20 78 4.3.6. The Wonky Grid . . . . . . . . . . . . . . . . . . . . 21 79 4.3.6.1. Wonky Grid Points at the Poles . . . . . . . . . . 23 80 4.3.6.2. Interpolation About the 180th Meridian . . . . . . 23 81 4.3.7. Temporal Interpolation . . . . . . . . . . . . . . . . 24 82 5. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 83 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 26 84 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26 85 8. Security Considerations . . . . . . . . . . . . . . . . . . . 26 86 9. Informative References . . . . . . . . . . . . . . . . . . . . 27 87 Appendix A. Sample Implementation . . . . . . . . . . . . . . . . 28 88 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 32 90 1. Introduction 92 A method for obscuring location information is described. This 93 method obscures location information such that it can be provided to 94 recipients without revealing the location of the subject to within 95 the desired distance. 97 Obscuring location has applications for protecting privacy, as 98 described in [I-D.ietf-geopriv-policy]. 100 This method uses a single configuration parameter as input: an 101 _obscuring distance_. 103 A location recipient (or recipient) is the entity that is given 104 location about a target entity. The goal is to ensure that the 105 recipient is unable to recover location information with better 106 accuracy than is desired. Despite this obscuring the recipient 107 should still be able to use the reported locations. 109 The obscuring process takes a series of _known locations_, which 110 might have greater accuracy than the recipient is permitted to 111 receive. The obscuring process produces a series of _reported 112 locations_. 114 2. Method Characteristics and Applicability 116 The method described here is intended to provide limited protection 117 for location information by constrained degradation. The method has 118 the following characteristics: 120 Simple Configuration: It might be possible to define a more complete 121 solution for obscuring location information that is more 122 configurable. However, a more configurable option would also 123 demand greater involvement from users so that they would be able 124 to specify a configuration that meets their goals. This method is 125 designed to be easy to understand, which increases the chances 126 that a user is able to successfully choose an appropriate 127 configuration. The method has just one input parameter: the 128 obscuring distance. 130 A separate parameter for the size of the grid used in the 131 algorithm can affect results; a fixed value is recommended in this 132 document. 134 Irreversible: Obscuring is intended to be irreversible. Information 135 is lost by applying the process. Multiple applications of this 136 process to the same input location is could reduce information 137 more than a single application of the process with the largest 138 obscuring distance. 140 Increases Uncertainty: A recipient does not need to treat obscured 141 location information any differently to location information that 142 contains uncertainty. The uncertainty of the reported location is 143 increased so that the reported location includes the known 144 location. Thus, the information that is reported is correct, 145 though the accuracy might be reduced. This document relies on a 146 definition of uncertainty for location described in more detail in 147 [I-D.thomson-geopriv-uncertainty]. 149 Two Dimensions: The method described in this document operates in 150 two dimensions only. Many of the principles might be applicable 151 in a higher number of dimensions, though no effort has been made 152 to validate their integrity. A three-dimensional location can be 153 reduced to a two-dimensional form for use in this algorithm. This 154 is not contrary to the goal of reducing the amount of information 155 provided. 157 Time Invariant: The method described in this document does not use 158 time. An entity performing obscuring does not need to consider 159 time in applying this method. Only the location is protected, not 160 the time that the location was determined. The time from the 161 known location is included in the reported location. 163 Obscuring Distance Not Secret: No attempt is made to protect the 164 obscuring distance as a secret. It is assumed that a recipient is 165 able to learn this value. 167 Minimal State: An entity that performs obscuring of locations often 168 performs this service for the combination of many targets and 169 recipients. This process requires only that the obscuring entity 170 hold maintain a trigger location for each recipient. The 171 additional state that an obscuring entity retains in order to 172 apply this obscuring method is a small increment over what is 173 typically required. The current known location does not need to 174 be retained; it need only be reacted to when it changes. 176 3. Obscuring Static Locations 178 A static location doesn't change. That is, different locations are 179 not attributed to a single target at different times. 181 The basic location obscuring case involves a single, isolated 182 instance of location information. 184 It might be appropriate to apply just this section in protecting the 185 privacy of a single location. A recipient must be unable to acquire 186 multiple location instances for the same entity if this is the only 187 form of obscuring used. 189 3.1. Known Point Locations 191 A known point location can be obscured by adding a randomized offset 192 vector to the location. The size of the offset vector is randomly 193 selected so that the reported location could be anywhere within the 194 obscuring distance of the known location, see Section 3.3. 196 The uncertainty of the reported location is set to the obscuring 197 distance. This ensures that the reported uncertainty region encloses 198 the known location. 200 Note: It's not sufficient to increase the uncertainty region so that 201 it minimally includes the known location. Doing this reveals that 202 the known location is at the boundary of the reported uncertainty 203 region. 205 3.2. Known Locations with Uncertainty 207 A known location with uncertainty is reduced to a circular 208 uncertainty region (see [I-D.thomson-geopriv-uncertainty], Section 209 4.2). An irregularly shaped uncertainty region is difficult to 210 evaluate against the scalar obscuring distance, and it might 211 inadvertently reveal more information than intended. 213 A known location with uncertainty greater than the obscuring radius 214 does not require additional obscuring. The radius of the circular 215 uncertainty region is compared to the obscuring distance to determine 216 if further obscuring is necessary. A location with sufficient 217 uncertainty can be directly reported. 219 Randomization is needed if the known location contains insufficient 220 uncertainty. As for a point location, an offset vector is added and 221 the uncertainty increased to the obscuring distance. A smaller 222 offset vector is necessary where the known location has uncertainty - 223 this vector need only be of a size up to the obscuring distance, less 224 the existing uncertainty. 226 The reported uncertainty is increased so that the reported location 227 contains an uncertainty radius of at least the obscuring distance. 228 An uncertainty in a known location cannot be recovered by a recipient 229 of an obscured location unless it is larger than the obscuring 230 distance. 232 Paradoxically, more accurate location determination methods are 233 better suited to obscuring. 235 A location that is reported with uncertainty does not always have 236 a uniform probability distribution. A non-uniform distribution is 237 not conducive to obscuring, since a location with an unevently 238 distributed probability distribution reveals that the location of 239 the target is more likely to be in specific parts of the 240 uncertainty region. 242 Information on the likely probability distribution cannot be 243 conveyed in many systems, including presence (see [RFC4119], 244 [RFC5491]). The location determination method can be reported, 245 which can reveal characteristics of the probability distribution. 246 Specific measures to counteract this effect are therefore not 247 feasible. 249 Removing or replacing the location determination method parameter 250 denies a recipient any information about probability distribution. 252 3.3. Selecting a Offset Vector 254 There are two methods that can be used to generate a random vector. 255 Both methods produce random vectors that are evenly distributed on 256 the plane within the maximum size. 258 The angle and distance (polar) method is considerably simpler, but it 259 is less well suited to the complete algorithm. The square peg method 260 is more conducive to the interpolation used. 262 Both methods take two uniformly distributed random numbers as input. 264 3.3.1. Angle and Distance Method 266 In the polar method, the first random value is used to select a 267 random angle, the second to select a random distance. 269 Assuming a "random()" function produces a number distributed between 270 0 (inclusive) and 1 (exclusive) - that is, the range [0, 1) - the 271 angle and length can be produced by the following: 273 angle = random() * 2 * pi 274 length = sqrt(random()) * size 275 or 276 length = (1 - |random() - random()|) * size 278 ...where "sqrt(x)" takes the square root of "x" and "|" takes the 279 absolute value of the enclosed. "size" is the desired size of the 280 random vector, which could be the obscuring distance less any 281 existing uncertainty. 283 3.3.2. Square Peg Method 285 In this method, the two random values are used to select a point in a 286 2x2 square between -1 and +1 on each axis. Vectors that are in the 287 direction of a corner are reduced in length so that the total length 288 of any vector is limited to 1 (as opposed to the square root of 2). 290 ^y 291 (-1,-1) | (1,1) 292 +-------,,---+---..-------+ 293 | ,-' | `-. | 294 | ,' | `._,| 295 | / | ,-'\ | 296 |/ | _,-' \| 297 | |,-' a | 298 -----+------------+------------+---->x 299 | | | 300 |\ | /| 301 | \ | / | 302 | `. | ,' | 303 | `-._ | _.-' | 304 +--------``--+--''--------+ 305 (-1,-1) | (1,-1) 307 The effect of this is that the probability of finding a value that is 308 toward the corners of the square (angles of PI/4, 3PI/4, -PI/4, 309 etc...) is twice the probability of finding a value along the axes 310 (angles of 0, PI/2, PI, etc...). This can be corrected by applying 311 the resulting cumulative distribution function to the angle. 313 x = random() * 2 - 1 314 y = random() * 2 - 1 315 length = sqrt(x*x + y*y) 316 angle = atan2(y, x) 317 a_side = round(angle * 2 / PI); 318 a_rem = angle - a_side * PI / 2 319 length = length * cos(a_rem) * size 320 angle = (tan(a_rem) / 8 + a_side / 4) * 2 * PI 322 ...where "atan2" produces the angle of the vector, "round(x)" 323 produces the nearest whole number to "x" and the cosine and tangent 324 functions are represented by "cos(x)" and "tan(x)" respectively. 326 This can be more efficiently calculated without trigonometric 327 functions using: 329 x = random() * 2 - 1 330 y = random() * 2 - 1 331 length = max(|x|, |y|) * size 332 if (x == 0) and (y == 0) 333 >> return zero length vector 334 if (|x| > |y|) 335 angle = PI * y / x / 4 336 else 337 angle = PI * (2 - x / y) / 4 338 if (y < -x) 339 angle = angle + PI 341 ...where "max(x, y)" chooses the more positive value of "x" and "y". 343 3.3.3. Randomness Requirements 345 A recipient that is able to learn the state of the random number 346 generator could use this to determine the offset vector. This would 347 reveal the known location based on a given reported location. A 348 secure pseudo-random number generator [RFC4086] provides an assurance 349 that recovering the state of the random number generator is made 350 considerably more difficult. 352 3.4. Multiple Reported Locations 354 Multiple applications of this algorithm produce different results. 355 The intersection of multiple reported locations can be used to 356 recover a better estimate of the known location. This recovered 357 estimate has less uncertainty than the obscuring distance, which is 358 not desirable. 360 Multiple reported locations for the same known location must not be 361 produced. An entity that is responsible for obscuring location might 362 achieve this by storing the reported location with the obscured 363 location. 365 It is possible to implement obscuring for a static location without 366 retaining state. Seeding a pseudo-random number generator with data 367 that is not available to the recipient can ensure that the same 368 result is produced from the same input. Taking a hash of the known 369 location combined with a secret key ensures that this seed cannot be 370 easily determined by a recipient (see Section 6.2 of [RFC4086] for 371 alternative methods). A hash function that uses the values shown in 372 Section 4.3.4 as input might be sufficient for this task. 374 4. Obscuring Changing Locations 376 Applications that use the location of a target over time, such as 377 presence [RFC4079] require additional steps to ensure that the 378 location a recipient acquires does not reveal more information than 379 desired. 381 The first consideration is the frequency of updates. As the target 382 moves, the known location changes. A frequently updated sequence of 383 reported locations could give a recipient sufficient information to 384 determine the known location with low uncertainty in a fashion close 385 to that described in Section 3.4. 387 Note: It is not necessary to ensure that a recipient always has 388 accurate location information. Early proposed algorithms wrongly 389 assumed that the reported location was required to cover the known 390 location at all times. Even in the absence of obscuring, changes 391 in location result in a recipient having outdated information. 392 The only necessary constraint is that the location be accurate at 393 the time that it is reported (or the time associated with that 394 report). 396 4.1. Update Conditions 398 To limit the amount of information provided to a recipient, new 399 reported locations are not generated in response to all changes in 400 the known location. The trigger for creating a new reported location 401 can be defined. 403 Any trigger condition needs to be constructed in a way that does not 404 reveal information. At the point that a new reported location is 405 provided to a recipient, the fact that the trigger conditions are met 406 at that point in time provides the recipient with significant 407 information that could - if the trigger conditions were poorly 408 defined - reveal significant information. 410 The goal is to provide a new reported location when the known 411 location moves by approximately the obscuring distance. This limits 412 the information that a recipient has available with similar accuracy 413 to each individual location. 415 4.1.1. Bad Triggers 417 One potential trigger is the movement of the target outside of the 418 reported uncertainty region. At the point that a new reported 419 location is generated, a recipient knows that the target is a) at the 420 boundary of the last uncertainty region, and b) somewhere in the new 421 uncertainty region. The intersection of these two regions produces 422 an area that is significantly smaller than desired. 424 New Reported 425 Location 426 ..--"""--.. ..--"""--.. / 427 .-' /=\. `-. 428 ,' ,' \\ `. 429 / / \\ \ 430 / / \\ \ 431 | | || | 432 | | || | 433 | | || | 434 \ \ // / 435 `. `. // \ .' 436 `._ `._// \ _.' 437 / `--..___..--' `--..__\..--' 438 Last Reported \ 439 Location Recovered Location 440 Along Border 442 Figure 1: Trigger on Leaving the Reported Location 444 Similarly, information is revealed if the trigger is movement based 445 on the known location. A new reported location might be produced 446 when the known location moves more than the obscuring distance from 447 the known location from the last report. 449 That is, when a new location is reported, the corresponding known 450 location is saved. A new reported location is determined when the 451 current known location is more than the obscuring distance from 452 the saved location. 454 If the recipient is able to assume that the target is moving in a 455 straight line, the speed of the target is revealed. 457 4.1.2. Hidden Trigger 459 To limit the information that is revealed at the point that a new 460 reported location is provided, the trigger conditions can be based on 461 information that is not available to the recipient. 463 Applying randomization to the trigger reduces the ability of a 464 recipient to make assertions about the significance of a new reported 465 location. 467 A hidden trigger is established using the following process: 469 o When a new reported location is generated: 471 1. The centroid of the known location is determined. 473 2. A random offset vector (Section 3.3) of a maximum size of half 474 the obscuring distance is determined. 476 3. The offset vector is added to the centroid and this value is 477 saved as a trigger point. 479 o When the known location changes: 481 1. The centroid of the (new) known location is determined. 483 2. If this centroid is further than the obscuring distance from 484 the saved trigger point, a new reported location is generated. 486 Each new reported location is randomized using the process described 487 in Section 3. 489 This algorithm ensures that the centroid of the known location moves 490 between 0.5 and 1.5 times the obscuring distance before a new 491 reported location is produced. As a consequence, the uncertainty in 492 the distance moved is equal to the obscuring distance. 494 4.2. Consecutive Reported Locations 496 The obscuring method has a weakness that is as a direct consequence 497 of the triggering conditions. These conditions grant a recipient 498 this information: 500 For any two consecutive reported locations there is a pair of 501 points that are less than 1.5 times the obscuring distance apart, 502 with one point in the area described by each reported location. 503 The first point is the known location at the time of the first 504 reported location; the second point is the known location at the 505 time of the second reported location. 507 At the time that a location is reported, the recipient can use this 508 knowledge to determine that the current location of the target is at 509 the intersection of the new reported location and a circle with a 510 radius of 2.5 times the obscuring distance, centered on the last 511 reported location, as shown in Figure 2 512 Known location . 513 is in overlap \ 514 Last \ \ New 515 ,.--"--.. \ \ ,.--"--.. 516 ,-' `-. \ |,-' `-. 517 / \ \_ + \ 518 | | /| | 519 | o |<---------->|| o | 520 | \ | --> 1.5OD \| | 521 \ \ / + / 522 `. \ ,' |`. ,' 523 `-..___,.+' ; `-..___,.-' 524 \ / 525 |<------>|<----\->|<------>|<-/---->|<------>|<--... 526 OD OD \ OD / OD OD 527 \ ,' 528 2.5OD \ / 529 \ _,' 530 _\/' OD = obscuring 531 _,,-' distance 533 Figure 2: Consecutive Reported Locations 535 Two consecutive reported locations can have their centers up to 3.5 536 times the obscuring distance apart; making the closest points on each 537 uncertainty region up to 1.5 times the obscuring distance apart. 538 When consecutive reported locations are maximally distant, a 539 recipient can recover the location of the target almost perfectly. 541 In general, the known location can be found by taking the 542 intersection of the current reported location and the preceding and 543 anteceding reported locations with their radius increased to 2.5 544 times the obscuring distance. 546 This relies on the recipient being able to determine the obscuring 547 distance. As long as the known location has lower uncertainty than 548 the obscuring distance at any point in time, the obscuring distance 549 is trivial to recover. 551 4.2.1. Reducing Variation between Offset Vectors 553 This shortcoming can be addressed by reducing the difference between 554 the random offset vector added to consecutive reported locations. 555 The extreme case shown in Figure 2 only arises because the absolute 556 difference between the randomization vector used for in consecutive 557 reported locations is twice the obscuring distance. The problem 558 occurs when the difference between consecutive known locations 559 approaches 1.5 times the obscuring distance in combination with this 560 large difference between randomization vectors. 562 Reducing the amount that a offset vector can change between 563 consecutive reported locations ensures that the most extreme 564 configuration cannot occur. 566 Using the same offset vector for all reported locations removes the 567 problem entirely. However, using the same offset vector increases 568 the probability of that vector being discovered and results a serious 569 problem if it is discovered. An adversary need only discover a 570 single known location for a specific reported location. For 571 instance, if the target is following a road, reported locations that 572 have a fixed offset from the known location will reveal the shape of 573 the road. From this it is trivial to learn the offset vector and 574 hence all past and future locations can be recovered. 576 Averaging is one potential approach to this problem. Each time a 577 location is randomized, the offset vector used can be the average of 578 a new random offset vector and the offset vector that was last used. 579 The proportion of old and new vectors determines the trade-off 580 between the probability that a recipient is able to learn a more 581 accurate location with the probability that a recipient is able to 582 learn the offset. 584 4.2.2. Trade-off in Reducing Variation 586 It is more difficult to learn an offset vector if additional 587 randomness is added to each new vector. An adversary that learns a 588 known location immediately has less information about subsequent 589 known locations based on the amount of additional randomness. As 590 long as the offset vector is able to change significantly as several 591 locations are reported, learning a limited number of offset vectors 592 is of limited use in recovering future known locations. 594 Too large a change in the offset vector increases the chances of 595 revealing the known location to a small area. Too small a change 596 provides an adversary that discovers a known location information 597 more information about subsequent known locations. A trade-off is 598 necessary. 600 The only way that the known location can be guaranteed to be unknown 601 over the entire area is when the offset vector doesn't change at all. 602 If the absolute difference in offset vectors is half the obscuring 603 distance, in the worst case the recipient is able to determine the 604 known location to be within 77 percent of the desired area. This 605 varies based on "o(diff)", as follows: 607 diff = | offset[x] - offset[x - 1] | / obscuring distance 608 a(diff) = ((1.5 + diff)^2 - 5.25) / (2*(1.5 + diff)) 609 o(diff) = acos(a(diff)) + 6.25 * acos((1.5 + diff - a(diff)) / 2.5) 610 - (1.5 + diff) * sqrt(1 - a(diff)^2) 612 ...where "acos(x)" returns the inverse cosine of "x". This only 613 produces a result where "diff" is less than 2. 615 It might be useful in this case to create a offset vector that is no 616 more than "diff" times the oscuring distance different to the 617 previous vector. This might be done by taking a weighted average of 618 the previous vector with a new random offset vector as follows: 620 o[new] = (o[prev] * (2 - diff) + o[random] * diff) / 2 622 ...where "o[new]" is the new ofset vector, "o[prev]" is the new 623 previous vector, and "o[random]" is a completely random vector of the 624 same magnitude. 626 4.3. Returning to the Same Location 628 A moving target might return to the same location several times. The 629 method described thus far produces a different reported location each 630 time. A recipient that is able to observe location over time could 631 intersect reported locations to recover the known location as long as 632 they make the assumption that the known location is the same each 633 time. 635 This can be extended to reveal a path that is habitually followed in 636 the same way. Each time the path is travelled, changing offset 637 vectors eventually reveal a more accurate view of the path. 639 4.3.1. Positional Stability 641 The key to addressing this flaw is to have the randomization of 642 offset vectors based on the known location. If the same known 643 location produced a reported location that was equal or very close to 644 it each time that the location was obscured, this would address the 645 problem. 647 It might be possible to take the coordinates of the known location 648 and pass them - along with a secret key - through a cryptographic 649 hash function. The resulting bits could be used as randomness that 650 produces an offset vector. This would ensure that the exact same 651 location always produces the same random vector. 653 The drawback of this sort of method is that the location is obscured 654 inconsistently when the known location changes even slightly. Such 655 imprecision is commonplace in location determination methods, 656 rendering this approach unsuitable. 658 The goal is to ensure that two known locations in close proximity 659 produce a constant (or near almost constant) random offset vector. 660 It is also desirable that the random vector change as the locations 661 change. This has the consequence of reducing the difference in 662 randomness between consecutive reported locations, provided that the 663 random values do not vary significantly over shorter distances (see 664 Section 4.2.1). The offset vector needs to change over a longer 665 distance to limit the amount that an adversary benefits from learning 666 both known and reported locations. 668 An approach similar to that described in [PERLIN] is used to achieve 669 a continuously varying random field. In this, randomness is 670 constrained to a grid of points with interpolation used to determine 671 values for intervening points. 673 4.3.2. Triggering with Positional Stability 675 No specific changes are required for the triggering process, though 676 this does require that some state be maintained by the entity that 677 performs obscuring. For a SIP entity that is maintaining a 678 subscription, this is not expected to be onerous. 680 The advantage of having a specific trigger for providing a new 681 reported location is that it reduces the information provided to a 682 recipient. Providing updates at a higher rate provide a recipient 683 with additional information that could be used to recover the offset. 685 4.3.3. Selecting a Grid 687 In selecting an appropriate grid with two dimensions, the curvature 688 of the surface of the Earth presents a challenge. The simplest 689 approach might be to select an origin at latitude 0, longitude 0. 690 Grid points could be placed at increments based on a constant ratio 691 between latitude and longitude and distance; for example, 9e-6 692 degrees per meter assumes a spherical planet of 6366197 meter radius, 693 which is slightly smaller than the semi-major axis of the ellipsoid 694 used in most Earth models. 696 For a two-dimensional grid with a multiple of "m", the following 697 equations identify the latitude and longitude of the four nearest 698 grid points to a given location: 700 grid = m * obscuring distance * 9e-6 702 latitude[low] = floor(latitude / grid) * grid 703 latitude[high] = latitude[low] + grid 705 longitude[low] = floor(longitude / grid) * grid 706 longitude[high] = longitude[low] + grid 708 ...where "floor(x)" produces the nearest whole integer that is more 709 negative than "x". 711 Grid intervals can be set to a multiple of the obscuring distance 712 that ensures that consecutive reported locations have continuously 713 varying offset vectors. These vectors need to change at a rate that 714 ensures maximum change over multiple reported locations without 715 causing too much information to be revealed from two consecutive 716 locations (as described in Section 4.2). Selecting a grid size is 717 discussed in more detail in Section 4.3.5.3. 719 The shortcoming of a grid of this nature is that changes in longitude 720 are more rapid as locations get closer to the poles. At 721 approximately 60 degrees of latitude (North or South), grid intervals 722 on the East-West direction are twice as frequent as desired. For 723 this reason, larger intervals between grid points might be chosen for 724 longitudes. 726 A solution for this problem is described in Section 4.3.6. An 727 alternative solution might use a local tangent plane, though this 728 introduces the problem of selecting an appropriate tangent plane as 729 locations change and providing consistent transitions between 730 different tangent planes. 732 In three dimensions, conversion to Earth-centered, Earth-fixed 733 Cartesian coordinates renders this problem moot. 735 4.3.4. Random Grid 737 At each of the points on the grid, a random offset vector is produced 738 using the method described in Section 3.3.2. Interpolation is used 739 to produce the offset vector for points within each grid cell, as 740 shown in Figure 3. 742 Rather than use a random number generator, random numbers are 743 produced using a cryptographic hash function. The input to this hash 744 might include: 746 o a secret known only by the entity that performs the obscuring with 747 sufficient entropy to render guessing ineffective (a random 748 sequence [RFC4086] is suitable for this purpose), 750 o the identity of the target, 752 o each individual coordinate of the grid point, and 754 o as necessary, a counter that allows for multiple random values to 755 be generated (for angle and distance, x and y, depending on the 756 method used to generate the random offset vector). 758 The inclusion of a secret ensures that a recipient is unable to 759 construct the offset vector. This secret is persistent so that later 760 applications of the obscuring formula do not produce a different 761 offset vector for the same location. 763 Section 3.3 requires that multiple random numbers are produced. The 764 additional identifier produces additional randomness where multiple 765 random (or pseudo-random) numbers are required. 767 Using a hash in this fashion ensures that each target gets a 768 different set of random offset vectors and that the same grid point 769 coordinates produce the same result. 771 Though ordering need only be consistent between consequent 772 applications of the obscuring algorithm, the following might be used 773 to produce random bits: 775 random = HMAC(secret key, target identity | identifier 776 | coordinate | coordinate | ...) 778 ...where "HMAC" is the hash MAC function [RFC2104] and "|" represents 779 concatenation, which might require a delimiter to terminate variable 780 length values. 782 Alternatively, the same sequence could be used to seed a secure 783 pseudo-random number generator [RFC4086]. Extracting values in the 784 same order makes the "identifier" unnecessary. 786 One consequence of this approach is that changes to the obscuring 787 distance result in the noise pattern being completely changed. This 788 can result in the same known location producing a significantly 789 different reported location before and after the change. 791 4.3.5. Linear Interpolation of Random Offsets 793 Once a grid of random offset vectors is established, an offset vector 794 is calculated based on the centroid of the known location. Figure 3 795 shows a centroid at the point "(x,y)" and the values that are used in 796 the interpolation process. 798 | | 799 - ---o------------------------------o--- 800 /| ^ /| 801 (x1,y2) | | (x2,y2) | 802 | | (y2-y) | 803 | (x,y) | | 804 | \ v | 805 |<-(x-x1)->X<------(x2-x)----->| 806 | ^ | 807 | | (y-y1) | 808 | v | 809 - ---o------------------------------o--- 810 /| /| 811 (x1,y1) | (x2,y1) | 813 Figure 3: Grid Interpolation 815 The offset vector at the identified point is produced by taking the 816 weighted average of the offset vectors. Two weighted averages are 817 taken between pairs of adjacent grid points along the same axis, then 818 the weighted average of the two resulting vectors is taken along the 819 other axis. 821 The following equations produce an linearly interpolated offset 822 vector for any point in this grid cell: 824 tx = (x - x1) / (x2 - x1) 825 ty = (y - y1) / (y2 - y1) 826 w1 = o[x1,y1] * (1 - tx) + o[x2,y1] * tx 827 w2 = o[x1,y1] * (1 - tx) + o[x2,y1] * tx 828 offset = w1 * (1 - ty) + w2 * ty 830 ...where "o[x1,y1]" is the random offset vector at the grid point 831 "(x1,y1)". 833 4.3.5.1. Uniformly Distributed Interpolation 835 A consequence of performing a weighted average is that the resulting 836 value is not uniformly distributed. Depending on the weighting 837 factor (the value "tx" or "ty" in Section 4.3.5), the resulting 838 probability distribution has a higher probability of producing values 839 in the middle of the range of possible values. 841 For example, the probability distribution for a weighted average of 842 two uniformly distributed random numbers between 0 and 1 is shown in 843 Figure 4. The figure shows the case where "t" is less than 0.5, 844 though the same distribution is produced for "t" and "(1-t)". 846 P(x) 847 | 848 | ,---------------. 849 | /: :\ 850 | / : : \ 851 | / : : \ 852 |/ : : \ 853 '----+---------------+------ x 854 0 t (1-t) 1 856 Figure 4 858 In order to correct for this skewing of results toward the middle of 859 the range, a smoothed interpolation is used. 861 Over the range from 0 to 1, the following produces a uniformly 862 distributed interpolation between "a" and "b": 864 r = a * (1 - t) + b * t 865 IF r < t AND r < (1 - t) THEN: 866 r = r * r / 2 / t / (1 - t) 867 ELSE IF r > t AND r > (1 - t) THEN: 868 r = 1 - (1 - r) * (1 - r) / t / (1 - t) 869 ELSE IF t < 0.5 THEN: 870 r = (2 * r - t) / 2 / (1 - t) 871 ELSE: 872 r = (2 * r - 1 + t) / 2 / t 874 This maps a linearly interpolated value to a smoothed value, using 875 the cumulative distribution function for the weighted sum of "a" and 876 "b". This mapping produces a value between 0 and 1 for inputs 877 between 0 and 1. The mapping is continuous. The mapping is not 878 monotonically increasing for some values of "a" and "b"; the intent 879 is to have a uniform distribution between 0 and 1, not between "a" 880 and "b". 882 For convenience, this interpolation function is represented in 883 shorthand throughout the remainder of the document: 884 "uniformDistInterp(a, b, t)". 886 Uniform interpolation alters the rate of change of the output. For a 887 proportional movement in "t" of "dt", the absolute change in output 888 is at most: 890 dr = 1 - (1 - dt)^2 892 Toward the middle of the range, for values of "a" and "b" that are at 893 the extents of the possible range and small values of "dt", changes 894 are magnified by up to two times their magnitude. 896 This interpolation function has similar characteristics to the 897 smoothing function used in [PERLIN], except that the goal is not 898 smoothing, but ensuring a uniform distribution of values in the 899 output. Values are continuous, but their first derivative is not. 901 4.3.5.2. Applying Uniformly Distributed Interpolation 903 The methods for producing random vectors described in Section 3.3 904 produce a result that is uniformly distributed in a circular area. 905 As a result, the cartesian coordinates produced are not evenly 906 distributed on each axis. Similarly, the polar coordinates have a 907 non-uniformly distributed magnitude. Rather than interpolate on the 908 output of this process, the uniformly distributed interpolation is 909 applied to the random inputs. 911 Interpolation is performed on a set of random numbers that are 912 produced at each grid vertex. This is used to produce a single set 913 of random numbers that are used as input to the random vector 914 algorithm. 916 A consequence of this process with the simple polar method described 917 in Section 3.3.1 is that the angle of the random vector does not 918 cross 360 degrees (2*pi) when being interpolated. In the worst case, 919 interpolation between two points requires rotation through almost 360 920 degrees. 922 The alternative method of interpolating angles - linear 923 interpolation using the shortest path - does produce an uniformly 924 distributed output, but it also produces a discontinuity that 925 could be exploited by a recipient when interpolation is applied in 926 more than one dimension. It is possible to produce a change in 927 the offset vector of up to twice the obscuring distance in size as 928 the known location moves only a short distance. 930 The more complicated square peg method (Section 3.3.2) results 931 produces evenly distributed values without this problem. 933 4.3.5.3. Selecting an Appropriate Grid Size 935 In the worst case, the polar method of generating a random vector in 936 combination with uniformly distributed interpolation can result in 937 twice the rate of rotation. Interpolation through a complete 360 938 degrees results in a maximum absolute change of: 940 d[p] = 2 * sin(pi * dr))) 942 ...where "dr" is the distance moved as a proportion of the obscuring 943 distance, which is no more than 0.5. 945 Using the maximum value from Section 4.3.5.1, the number of multiples 946 required to limit movement can be calculated using: 948 m[p] = 1.5 / (1 - sqrt(1 - asin(d[p] / 2) / pi)) 950 For an absolute change in the random vector of no more than the 951 obscuring distance, the grid needs to be at least 17.22 multiples of 952 the obscuring distance. If the absolute change is only half this 953 amount, the grid needs to be larger, at 36.53 multiples of the 954 obscuring distance. 956 Using such a large grid to deal with a low probability case is 957 suboptimal. The square peg method allows for a much smaller grid, 958 with a maximum absolute change being dependent on only the increased 959 rate of change produced by the interpolation method: 961 d[sp] = 2 * dr 962 = 2 * (1 - (1 - 1.5 / m[sp])^2) 963 m[sp] = 1.5 / (1 - sqrt(1 - d[sp] / 2)) 965 This means that a grid of 5.12 times the obscuring distance limits 966 absolute difference in the offset vector to obscuring distance; a 967 grid of 11.20 times the obscuring distances limits the difference to 968 half. 970 Selecting a grid size at 8 times the obscuring distances ensures that 971 the absolute change in offset vector is 0.680 times the obscuring 972 distance. A complete change in offset vector can then occur after 973 linear movement of only 8 times the obscuring distance. In the worst 974 case, movement reveals a location within 66.0% of the area of a 975 circle with a radius of the obscuring distance. 977 4.3.6. The Wonky Grid 979 To address the concerns caused by the curvature of the Earth, a 980 modified grid-like structure can be used. It is not strictly 981 necessary that the grid be absolutely grid-like in structure. 982 Therefore, it's possible that different grid intervals could be 983 selected. 985 This structure uses a different interval for points at different 986 latitudes, at the selected low latitude: 988 grid[llat] = grid / cos(latitude[low]) 989 longitude[low,llat] = floor(longitude / grid[llat]) * grid[llat] 990 longitude[high,llat] = longitude[low,llat] + grid[llat] 992 ...and at the high latitude: 994 grid[hlat] = grid / cos(latitude[high]) 995 longitude[low,hlat] = floor(longitude / grid[hlat]) * grid[hlat] 996 longitude[high,hlat] = longitude[low,hlat] + grid[hlat] 998 ...where "cos(x)" produces the cosine of "x". 1000 This produces fewer grid points for latitudes that are further from 1001 the Equator. At the poles (and above), a single offset vector is 1002 sufficient. 1004 Interpolation of these points uses four distinct points, as shown in 1005 Figure 5. 1007 (x-x1_2) (x2_2-x) 1008 |<-------->|<----------------->| 1009 | | | 1010 - ---o------------------------------o--- - 1011 /| | ^ |\ 1012 (x1_2,y2) : | | : (x2_2,y2) 1013 | | (y2-y) 1014 (x,y) ' | 1015 \ v 1016 X - ------ 1017 ^ 1018 : . : | (y-y1) 1019 | | | v 1020 - ---o---------------------------o--------------- - 1021 /| | |\ 1022 (x1_1,y1) |<--------------------->|<->| (x2_1,y1) 1023 (x-x1_1) (x2_1-x) 1025 Figure 5: Wonky Grid Interpolation 1027 Linear interpolation uses the amended equations: 1029 tx_1 = (x - x1_1) / (x2_1 - x1_1) 1030 w1 = uniformDistInterp(r[x1_1,y1], r[x2_1,y1], tx_1) 1031 tx_2 = (x - x1_2) / (x2_2 - x1_2) 1032 w2 = uniformDistInterp(r[x1_2,y2], r[x2_2,y2], tx_2) 1034 Note that this uses the uniformly distributed random values selected 1035 at each grid point, rather than the offset vectors. Each random 1036 value is a uniformly distributed random value in the range [0, 1). 1038 4.3.6.1. Wonky Grid Points at the Poles 1040 At 90 degrees North and South, the cosine used to determine the wonky 1041 grid produces a zero. This produces an undefined grid spacing. 1043 To avoid this problem, produce a single value at each pole: (90, 0) 1044 and (-90, 0). This value replaces "w1" or "w2" in the interpolation 1045 equations. Retaining the same weighting (that is, "ty") for 1046 determining the final offset is desirable, so that the rate of change 1047 is not artificially increased. 1049 4.3.6.2. Interpolation About the 180th Meridian 1051 At 180 degrees East (or West), longitude values cross from positive 1052 to negative values. This produces a discontinuity in the values 1053 used. This could be exploited to learn when the known location cross 1054 the 180th meridian. 1056 180/-180 180/-180 1057 | | 1058 +ve: x1a | x2a x1a | x2a 1059 ---o---o--X--------o---o--- ... ---o---o--X--------o---o--- 1060 x1b | x2b x1b | x2b 1061 . | . . | . 1062 | | | | 1063 |<------------->| |<------------->| 1064 overlap = grid interval overlap = grid interval 1066 Figure 6: Interpolation About 180 Degrees 1068 This problem might only manifest for one of the two interpolations 1069 performed across changing longitude values in a wonky grid. To 1070 address this, the values produced by the negative and positive 1071 aspects are independently generated, then these values are 1072 interpolated over a span of one grid interval. 1074 For any point within half of one grid interval from the 180th 1075 meridian, this algorithm is used. Perform interpolation using the 1076 selected grid points, then add or subtract 360 degrees from the 1077 original value to get a value that is either more than 180 degrees or 1078 less than -180 degrees. Perform interpolation on this second point. 1080 The two interpolated values are then interpolated using a different 1081 proportion. This interpolation is taken on the overlap interval that 1082 crosses the 180th meridian, as shown in the Figure 6. This 1083 proportion is produced by taking the positive input value (that is, 1084 the longitude value, with 360 degrees added if it is negative) and 1085 applying the following: 1087 grid = m * obscuring distance * 9e-6 / cos(latitude) 1088 IF longitide + grid / 2 > 180 OR longitude - grid / 2 < -180 THEN: 1089 t = ((longitude + 360) % 360 - 180 - grid / 2) / grid 1090 random[o] = uniformDistInterp(random[+ve], random[-ve], t) 1091 ENDIF 1093 ...where "%" represents the modulo operation. The final interpolated 1094 value is determined using the uniformly distributed weighted average 1095 method described in Section 4.3.5.1. 1097 4.3.7. Temporal Interpolation 1099 Providing different values over time is difficult to balance against 1100 the need to obscure the same location in the same way. It is 1101 possible to add additional dimensions upon which to interpolate the 1102 offset vector. Adding time as one such dimension would allow the 1103 offset vector to change gradually over time as well as with respect 1104 to space. 1106 A form of temporal interpolation might allow the obscuring entity to 1107 change the secret key that it maintains over time. However, this 1108 does not provide positional stability unless the interpolation is 1109 performed over a period that is significantly longer than the period 1110 over which the known location might return to the same location. 1111 Changing the offset vector applied to the same location would negate 1112 much of the benefit derived from the algorithm. 1114 In practice, the period over which the offset would change would have 1115 to be significantly longer than the time taken for all potential 1116 visited locations to completely change in all aspects. This implies 1117 that temporal interpolation is likely only useful on geological time 1118 scales. 1120 5. Examples 1122 Obscuring a known location at latitude -34.401072, longitude 1123 150.636361 with 100 meter obscuring distance first requires 1124 calculation of the grid size and the grid points: 1126 gridsize = 8 * obscuring_distance * 9e-6 = 0.0072 1128 Once that is determined, the two latitude values used for the grid 1129 are determined: 1131 lowlat = floor(-34.401072 / 0.0072) * 0.0072 = -34.4016 1132 highlat = lowlat + 0.0072 = -34.3944 1134 For each latitude value, two longitude values are determined using a 1135 modified grid size to find the final set of of grid points: 1137 Note: Intermediate values in this example are rounded for 1138 presentation purposes. 1140 grid[lowlat] = gridsize / cos(lowlat * pi / 180) = 0.0087262 1141 lowlng[lowlat] = floor(150.636361 / 0.0087262) * 0.0087262 1142 = 150.632339 1143 highlng[lowlat] = lowlng[lowlat] + 0.0087262 = 150.641066 1144 grid[highlat] = 0.0087255 1145 lowlng[highlat] = 150.628105 1146 highlng[highlat] = 150.636831 1148 This gives a set of points for which random values are produced. The 1149 actual random values used depend on many factors (see Section 4.3.4). 1150 The following values are used in this example: 1152 random[-34.4016, 150.632339] = 0.4228538586758077 1153 random[-34.4016, 150.641066] = 0.9430289615411311 1154 random[-34.3944, 150.628105] = 0.9174296103883535 1155 random[-34.3944, 150.636831] = 0.008725488356129405 1157 The random values are interpolated along the same latitude using a 1158 "t" value that is based on the distance from the corresponding low 1159 longitude value. The two resulting values are interpolated along the 1160 same longitude using a "t" value that is based on the distance from 1161 the low latitude value. Uniformly distributed interpolation is used 1162 in both cases. 1164 t[-34.4016] = (150.636361 - 150.632339) / 0.0087262 = 0.460866 1165 r[-34.4016] = 0.770898 1166 t[-34.3944] = (150.636361 - 150.628105) / 0.0087255 = 0.946145 1167 r[-34.3944] = 0.440578 1168 t = (-34.401072 - -34.4016) / 0.0072 = 0.0733055 1169 r = 0.7661978449732944 1171 This first random value is used for the "x" component. A second 1172 random value for "y" is chosen using the same process, producing 1173 0.16585607985072537. 1175 These values are then input into the square peg algorithm: 1177 d = 100 * max(0.7661978449732944, 0.16585607985072537) 1178 = 76.61978449732944 1179 -- since |x| > |y| 1180 a = y * pi / x / 4 = 5.3380813420741795 1181 -- no further change since y > -x 1183 Therefore, the location is moved 76.62 meters on a bearing of 305.84 1184 degrees. The resulting reported location is moved along the local 1185 tangent plane to {-34.400719, 150.635772} and a circle of 100 meter 1186 radius is described. 1188 Finally, a random point is chosen within 50 meters of the original 1189 point. No more location is provided until the known location moves 1190 more than 100 meters from that point. In this case, the trigger 1191 point is set to {-34.401388, 150.636471}. If the known location is 1192 updated to {-34.401816, 150.636361}, no new location is reported. 1194 Moving to {-34.400621, 150.635717} is more than 100 meters from the 1195 trigger point, even though this is very close to the last reported 1196 location. This results in a new location being reported at 1197 {-34.400346, 150.634929}. 1199 6. Acknowledgements 1201 Thanks go to Robert Sparks for identifying key shortcomings in early 1202 attempts to obscure location. Richard Barnes, Jorge Cuellar, Cullen 1203 Jennings, Warren Kumari, and Hannes Tschofenig variously provided 1204 input, feedback, criticisms and insightful ideas. 1206 7. IANA Considerations 1208 This document has no IANA actions. 1210 [RFC Editor: please remove this section prior to publication.] 1212 8. Security Considerations 1214 This document describes a method for obscuring location. An effort 1215 has been made to ensure that reported locations do not reveal any 1216 more information than the input dictates. However, obscuring 1217 location is not a substitute for withholding location information if 1218 the goal is to ensure that a recipient remains ignorant of the known 1219 location. Alternatively, a recipient might be provided with 1220 completely falsified location information. 1222 There is little point in obscuring location when other location- 1223 related information is included in a composite document, like a 1224 presence document [RFC3863]. Removing other information, such as 1225 dynamic location information [RFC5965] is necessary to ensure that 1226 this cannot be used to recover the known location. 1228 A reported location can inadvertently reveal far more information 1229 than intended to a recipient in possession of additional information. 1230 A recipient might be able to apply this additional information to 1231 determine the location of the target with less uncertainty than 1232 desired. Additional information includes information about the 1233 reported location or information about the Target. 1235 For instance, a recipient with a map might be able to identify areas 1236 on that map that a target is more likely to be found. A recipient 1237 can combine any additional information with the knowledge that the 1238 reported location is correct at the time it is reported to recover a 1239 better estimate of the known location. Aside from map-based data, 1240 other information that could be used to acquire a more accurate 1241 estimate of the location of a target might include knowledge of the 1242 target's past behavior, personality traits, or aggregated demographic 1243 data. 1245 Increasing the obscuring distance might increase the uncertainty in 1246 the location that a recipient with additional information can 1247 ultimately recover. The complexity involved and the large volume of 1248 additional data involved makes more specific measures difficult. 1250 9. Informative References 1252 [I-D.ietf-geopriv-arch] 1253 Barnes, R., Lepinski, M., Cooper, A., Morris, J., 1254 Tschofenig, H., and H. Schulzrinne, "An Architecture for 1255 Location and Location Privacy in Internet Applications", 1256 draft-ietf-geopriv-arch-03 (work in progress), 1257 October 2010. 1259 [I-D.ietf-geopriv-policy] 1260 Schulzrinne, H., Tschofenig, H., Morris, J., Cuellar, J., 1261 and J. Polk, "Geolocation Policy: A Document Format for 1262 Expressing Privacy Preferences for Location Information", 1263 draft-ietf-geopriv-policy-23 (work in progress), 1264 March 2011. 1266 [I-D.thomson-geopriv-uncertainty] 1267 Thomson, M. and J. Winterbottom, "Representation of 1268 Uncertainty and Confidence in PIDF-LO", 1269 draft-thomson-geopriv-uncertainty-06 (work in progress), 1270 March 2011. 1272 [PERLIN] Perlin, K., "An Image Synthesizer", ACM SIGGRAPH Computer 1273 Graphics v.19 n.3, p.287-296, July 1985. 1275 [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- 1276 Hashing for Message Authentication", RFC 2104, 1277 February 1997. 1279 [RFC3863] Sugano, H., Fujimoto, S., Klyne, G., Bateman, A., Carr, 1280 W., and J. Peterson, "Presence Information Data Format 1281 (PIDF)", RFC 3863, August 2004. 1283 [RFC4079] Peterson, J., "A Presence Architecture for the 1284 Distribution of GEOPRIV Location Objects", RFC 4079, 1285 July 2005. 1287 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness 1288 Requirements for Security", BCP 106, RFC 4086, June 2005. 1290 [RFC4119] Peterson, J., "A Presence-based GEOPRIV Location Object 1291 Format", RFC 4119, December 2005. 1293 [RFC5491] Winterbottom, J., Thomson, M., and H. Tschofenig, "GEOPRIV 1294 Presence Information Data Format Location Object (PIDF-LO) 1295 Usage Clarification, Considerations, and Recommendations", 1296 RFC 5491, March 2009. 1298 [RFC5965] Shafranovich, Y., Levine, J., and M. Kucherawy, "An 1299 Extensible Format for Email Feedback Reports", RFC 5965, 1300 August 2010. 1302 Appendix A. Sample Implementation 1304 This javascript implements the obscuring algorithm. 1306 /** 1307 * Location obscurer: 1308 * var f = new GeoShape.Fuzzer(100, secret, target); 1309 * var reported = f.fuzz(known); 1310 * This object retains state. 1311 */ 1312 GeoShape.Fuzzer = function(dist, secret, targetIdentity) { 1313 this.distance = dist; 1314 var key = Hash.HMAC(secret, targetIdentity, Hash.SHA1); 1315 this.random = new GeoShape.UIRandom(key, dist); 1316 this.trigger = null; 1317 this.used = 0; 1318 return this; 1319 }; 1320 GeoShape.Fuzzer.prototype = { 1321 /** 1322 * Main obscuring function. 1323 * @param {GeoShape} a shape 1324 * @returns {GeoShape.GeoCircle} a fuzzed circle 1325 */ 1326 fuzz: function(shape) { 1327 var cu = shape.to2d().calculateCentroid(); 1328 /* 1329 * cu contains two attributes: 1330 * centroid: a WGS84 point; uncertainty: a distance in metres 1331 */ 1332 if (!cu.uncertainty) { 1333 cu.uncertainty = 0; 1334 } 1335 if (this.hasMoved(cu.centroid)) { 1336 var addunc = Math.max(0, this.distance - cu.uncertainty); 1337 var centre = this.fuzzPoint(cu.centroid, addunc); 1338 var unc = Math.max(cu.uncertainty, this.distance); 1339 this.fuzzed = new GeoShape.GeoCircle(centre, unc); 1340 var td = this.distance / 2; 1341 this.trigger = this.randomize(cu.centroid, td); 1342 this.used = 0; 1343 } 1344 this.used++; 1345 return this.fuzzed; 1346 }, 1347 /** 1348 * Determine if the location has moved sufficient distance 1349 * from the trigger to require fuzzing. 1350 */ 1351 hasMoved: function(centroid) { 1352 if (!this.trigger) { 1353 return true; 1354 } 1355 return this.trigger.distanceTo(centroid) > this.distance; 1356 }, 1357 /** 1358 * Use a continuously varying random grid to move a point. 1359 */ 1360 fuzzPoint: function(point, dist) { 1361 this.random.reset(); 1362 var x = this.random.next(point.lat, point.lng) * 2 - 1; 1363 var y = this.random.next(point.lat, point.lng) * 2 - 1; 1364 if (x === 0 && y === 0) { 1365 return point; 1366 } 1367 var d = dist * Math.max(Math.abs(x), Math.abs(y)); 1368 var a; 1369 if (Math.abs(x) > Math.abs(y)) { 1370 a = y / x; 1371 } else { 1372 a = 2 - x / y; 1373 } 1374 if (y < -x) { 1375 a += 4; 1376 } 1377 return point.movePoint(d, a * Math.PI / 4); 1378 }, 1379 /** 1380 * Move a point randomly (polar method). 1381 */ 1382 randomize: function(point, dist) { 1383 var d = Math.sqrt(Math.random()) * dist; 1384 var a = Math.random() * 2 * Math.PI; 1385 return point.movePoint(d, a); 1386 } 1387 }; 1389 /** 1390 * A uniformly distributed, interpolated, pseudorandom number 1391 * generator that produces the same value for the same key, 1392 * location and grid size. 1393 * 1394 * @param secret a unique, secret key sequence 1395 * @param gridSize the desired size of the grid, in metres 1396 */ 1397 GeoShape.UIRandom = function(secret, gridSize) { 1398 this.key = secret; 1399 this.grid = 8 * gridSize * 9e-6; 1400 this.reset(); 1401 return this; 1402 }; 1403 GeoShape.UIRandom.prototype = { 1404 /** 1405 * Get next pseudorandom value for a latitude and longitude. 1406 */ 1407 next: function(lat, lng) { 1408 var lowlat = Math.floor(lat / this.grid) * this.grid; 1409 var bottom = this.interpLongitude(lowlat, lng); 1410 var top = this.interpLongitude(lowlat + this.grid, lng); 1411 var tlat = (lat - lowlat) / this.grid; 1412 this.rCount++; /* next time produces a different answer */ 1413 return this.uniformDistInterp(bottom, top, tlat); 1414 }, 1415 reset: function() { 1416 this.rCount = 0; 1417 }, 1418 /* Takes a point and produces a "random" value. */ 1419 hashRandom: function(lat, lng) { 1420 /* need to fix the lat and lng: 7 decimal places */ 1421 var flat = Math.round(lat * 1e7).toString(); 1422 var flng = Math.round(lng * 1e7).toString(); 1424 var input = [].concat(this.rCount, UTF8(flat), 1425 0xff, UTF8(flng)); 1426 var h = Hash.HMAC(this.key, input, Hash.SHA1); 1427 var r = 0; 1428 for (var i = 0; i < h.length; ++i) { 1429 r ^= h[i] << ((i % 4) * 8); 1430 } 1431 /* add 0.5 to deal with sign bit */ 1432 return r / Math.pow(2, 32) + 0.5; 1433 }, 1434 /* interpolate a and b using t, with a uniform distribution */ 1435 uniformDistInterp: function(a, b, t) { 1436 var r = a * (1 - t) + b * t; 1437 if (r < t && r < (1 - t)) { 1438 r = r * r / 2 / t / (1 - t); 1439 } else if (r > t && r > (1 - t)) { 1440 r = 1 - (1 - r) * (1 - r) / 2 / t / (1 - t); 1441 } else { 1442 r = 0.5 + (r - 0.5) / Math.max(t, 1 - t); 1443 } 1444 return r; 1445 }, 1446 interpLongitude: function(lat, lng) { 1447 if (Math.abs(lat) >= 90) { 1448 return this.hashRandom((lat > 0) ? 90 : -90, lng); 1449 } 1450 var size = this.grid / Math.cos(lat * Math.PI / 180); 1451 if ((lng - size / 2) < -180 || (lng + size / 2) > 180) { 1452 var lngpos = (lng + 360) % 360; 1453 var rpos = this.interpLongSimple(lat, lngpos, size); 1454 var lngneg = lngpos - 360; 1455 var rneg = this.interpLongSimple(lat, lngneg, size); 1456 var t = ((lng + 360) % 360 - 180 - size / 2) / size; 1457 return this.uniformDistInterp(rpos, rneg, t); 1458 } 1459 return this.interpLongSimple(lat, lng, size); 1461 }, 1462 interpLongSimple: function(lat, lng, size) { 1463 var lowlng = Math.floor(lng / size) * size; 1464 var rlow = this.hashRandom(lat, lowlng); 1465 var rhigh = this.hashRandom(lat, lowlng + size); 1466 var t = (lng - lowlng) / size; 1467 return this.uniformDistInterp(rlow, rhigh, t); 1468 } 1469 }; 1471 Author's Address 1473 Martin Thomson 1474 Andrew Corporation 1475 Andrew Building (39) 1476 Wollongong University Campus 1477 Northfields Avenue 1478 Wollongong, NSW 2522 1479 AU 1481 Phone: +61 2 4221 2915 1482 Email: martin.thomson@andrew.com