Permissions and roles are provided by the User module. The user.permissions service discovers the permissions.yml provided by installed modules. By default, the service is defined through the \Drupal\user\PermissionHandler class.
Drupal does not save a list of all permissions that are available. The permissions for a system are loaded when the permissions page is loaded. Roles contain an array of permissions.
When checking a user's access for a permission, Drupal checks all the user's roles to see whether they support that permission.
You can pass an undefined permission to a user access check and not receive an error. The access check will simply fail unless the user is UID 1, which bypasses access checks.